Хотын автобусны буудлуудын хоорондын замын мэдээллийг дараах байдлаар өгсөн байна.

• Буудал бүр → нэг орой (node)
• Зам бүр → (u, v) гэсэн хосоор өгөгдөнө

Гэхдээ эдгээр замуудын мэдээлэл нь чиглэлтэй (directed) байдлаар бичигдсэн байж магадгүй.

? Зорилго

? Өгөгдсөн бүх замыг ашиглаад:

Энэ сүлжээг чиглэлгүй (undirected) graph гэж үзэх боломжтой юу?

? Нөхцөл

Graph нь undirected байхын тулд:

? Хэрэв (u, v) зам байвал
? заавал (v, u) зам мөн байх ёстой

Оролт:

Эхний мөрөнд хоёр бүхэл тоо өгөгдөнө:

N M

• N — буудлын тоо
• M — өгөгдсөн замын тоо

Дараагийн M мөр бүрт:

u v

• u → v чиглэлтэй зам байна

Гаралт:

• Хэрэв бүх замууд харилцан хос байвал:YES
• Үгүй бол:NO

Хязгаарлалтууд:

• 1 ≤ N ≤ 100000
• 0 ≤ M ≤ 100000
• 1 ≤ u, v ≤ N

Дэд бодлого

Жишээ:

Оролт-1

3 4
1 2
2 1
2 3
3 2

Гаралт-1

YES

Тайлбар

Бүх edge-үүд хос байна:

• 1 ↔ 2
• 2 ↔ 3

Оролт-2

3 3
1 2
2 1
2 3

Гаралт-2

NO

Тайлбар

• 2 → 3 байна
• Харин 3 → 2 байхгүй ❌

Оролт

2 1
1 2

Гаралт

NO

Тайлбар

• 1 → degree 4
• бусад → degree 1 → leaf

? Хариу = 4