Бат хөдөөнөөс Улаанбаатар хотод ахынхаа гэрт иржээ.

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

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

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

? Зорилго

Бат ахынхаа гэрээс (1-р буудал) гарч:

• өөр өөр буудлуудаар дамжин явж
• дахин 1-р буудалдаа буцаж ирэхийг хүсэж байна

? Өөрөөр хэлбэл:

1-р буудлаас эхэлсэн cycle ол

⚠️ Нөхцөл

• Зам давтаж явж болно, гэхдээ буудлыг давтахгүй (cycle)
• 1-р буудлаас эхэлж 1-р буудалд дуусна
• Дамжсан буудлууд аль болох олон байх ёстой

? Таны хийх зүйл

? Хэрэв ийм cycle байх бол:

• дамжих буудлуудын дарааллыг хэвлэ

? Хэрэв боломжгүй бол: -2

⚖️ Нэмэлт нөхцөл

? Хэрэв олон боломж байвал:

• лексикографик хамгийн бага дараалал-ыг хэвлэнэ

Оролт:

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

N M

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

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

u v

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

Гаралт:

Хэрэв боломжтой бол:

k a1 a2 a3 ... ak

• k — буудлын тоо (cycle length)
• a1 = 1, ak = 1

? Боломжгүй бол: -2

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

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

Дэд бодлого

Жишээ:

Оролт-1

3 3
1 2
2 3
3 1

Гаралт-1

4
1 2 3 1

Оролт-2

4 3
1 2
2 3
3 4

Гаралт-2

-2

Оролт-3

5 6
1 2
2 3
3 1
1 4
4 5
5 1

Гаралт-3

4
1 2 3 1