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

Бид энэ сүлжээг дараах байдлаар загварчилна:

• Буудал бүр → нэг орой (node)
• Зам бүр → ирмэг (edge)

? Энэ graph нь чиглэлгүй (undirected) гэж үзнэ.

? Зорилго

? Өгөгдсөн graph-д:

тойрог (cycle) байгаа эсэхийг шалга.

? Тойрог (cycle) гэж юу вэ?

? Хэрэв нэг node-оос эхлээд:

• edge-үүдээр явж
• дахин өөрийгөө хүрч чадвал

? энэ нь cycle гэж үзнэ.

Оролт:

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

N M

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

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

u v

• u болон v буудлын хооронд зам байна

Гаралт:

• Хэрэв cycle байвал:YES
• Үгүй бол:NO

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

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

Дэд бодлого

Жишээ:

Оролт-1

4 3
1 2
2 3
3 4

Гаралт-1

NO

Оролт-2

3 3
1 2
2 3
3 1

Гаралт-2

YES

Оролт-3

5 4
1 2
2 3
3 1
4 5

Гаралт-3

YES