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

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

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

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

? Зорилго

? Өгөгдсөн graph нь мод (tree) мөн эсэхийг шалга.

? Мод (Tree) гэж юу вэ?

Graph нь мод байх нөхцөл:

1. ✅ Cycle байхгүй
2. ✅ Бүх node хоорондоо холбогдсон (connected)

? Эсвэл equivalently:

M = N - 1

мөн graph connected байвал → tree

Оролт:

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

N M

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

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

u v

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

Гаралт:

• Хэрэв graph мод бол: YES
• Үгүй бол: NO

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

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

Дэд бодлого

Жишээ:

Оролт-1

4 3
1 2
2 3
3 4

Гаралт-1

YES

Оролт-2

4 4
1 2
2 3
3 4

Гаралт-2

NO

Оролт-3

4 2
1 2
3 4

Гаралт-3

NO