Хотын автобусны буудлуудын сүлжээг дараах байдлаар өгсөн байна.

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

Гэхдээ өгөгдсөн сүлжээ нь алдаатай байж магадгүй.

? Зорилго

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

? Энгийн граф гэж юу вэ?

Graph нь энгийн байх нөхцөл:

1. ❌ Self-loop байхгүй

   • (u, u) хэлбэрийн edge байх ёсгүй

2. ❌ Давхардсан edge байхгүй

   • (u, v) болон (v, u) нь нэг edge гэж үзнэ
   • Ийм edge олон удаа давтагдах ёсгүй

Оролт:

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

N M

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

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

u v

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

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

Гаралт:

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

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

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

Дэд бодлого

Жишээ:

Оролт-1

3 2
1 2
2 3

Гаралт-1

YES

Оролт-2

3 2
1 1
2 3

Гаралт-2

NO

Оролт-3

3 3
1 2
2 1
1 2

Гаралт-3

NO

Тайлбар

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

? Хариу = 4