E. Харри Поттер ба Хөдөлдөг Шат

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Харри Поттер үл үзэгдэгч цуваа сургуулийн харгалзагч Фличээс зугтаж явахдаа алга болгочихжээ. Үл үзэгдэгч зүйл хайна гэдэг бол амаргүй зүйл ч, аз болоход найзууд нь туслахад бэлэн байв. Хермоний Гренжер "Үл үзэгдэгч цув ба түүний талаарх бүх зүйлс", "Графын хамгийн богино зам", "Сүлжээний урсгал (Network flow)", "Хамгийн их утгатай өсөх дэд дараалал", "Шидэт биетүүдийн нэвтэрхий толь" зэрэг номнуудыг уншжээ. Тэрээр аль хэдийн хэт динамик системээс (Хогвартс бол тэдний нэг) үл үзэгдэгч цувыг хайх хайлтын алгоритмыг боловсруулсан байлаа.

Хогвартс нь $1$-ээс $n$ хүртэлх бүхэл тоогоор дугаарлагдсан $n$ давхраас бүрдэнэ. Зарим давхрууд хоорондоо шатаар холбогдсон байх ба шат нь аль нэг үзүүрийнхээ байрлалыг өөрчилж болзошгүй. Өөрөөр хэлбэл шат ($a$, $b$) давхарыг хооронд нь холбодог байлаа гэхэд нэг үзүүрийнх нь байрлал өөрчлөгдвөл ($a$, $c$) хоёр давхрыг холбох юм уу, ($b$, $c$) давхрыг холбодог болно. (Энд $c$ давхар нь $a$, $b$-ээс өөр аль нэг давхар). Зарим үед хоёр давхрыг хооронд нь олон шатаар холбодог байж болно.

Харри одоогоор $1$-р давхарт байгаа. Тэр хэд дэхь давхарт цуваа гээснээ санахгүй байгаа учраас бүх давхруудаар шалгаж үзэхийг хүсчээ. Тэгэхлээр түүний зорилт бол давхар бүрт ядаж нэг удаа очих бөгөөд ямар ч дарааллаар очиж болно. Мөн хайлтаа аль ч давхарт дуусгаж болно.

Одоо үед шатнууд өөрсдөө хөдлөхөө бараг больсон боловч Рон, Хермоний хоёр Харрид туслахын тулд ямар нэг шившлэг хэрэглэн шатыг хөдөлгөж болохоор байв. Бусдад аль болох мэдэгдэхгүйн тулд гурван найз шатыг нэг нэгээр нь хөдөлгөх бөгөөд шат бүрийг зөвхөн нэгээс илүүгүй хөдөлгөх ёстой. Шатнууд хөдөлж байх үед Харри давхруудаар явж болох бөгөөд тухайн давхарт хүрэнгүүтээ цуваа олж чадна. Бас эрэл хайгуул хийж байх үед шатнууд өөрсдөө хөдлөхгүй.

Гурван найзад хайлтын төлөвлөгөө боловсруулахад нь туслаарай. Олон боломжит хариу олдвол алийг нь ч бичсэн болно.

Оролт

Эхний мөрөнд давхрын тоо $n$ ба шатны тоо $m$ ($1 ≤ n ≤ 100000$, $0 ≤ m ≤ 200000$) байна. Дараагийн $m$ мөрөнд мөр бүрд шатны холбож байгаа давхруудыг илэрхийлэх хос тоонууд байна.

Гаралт

Эхний мөрөнд хэрэв Харри бүх давхраар хайлт хийх боломжтой бол "YES" (хашилтгүйгээр) үгүй бол "NO" гэж хэвлээрэй. Хэрвээ боломжит хариу олдсон бол дараагийн мөрөнд Рон, Хермоний хоёрын хөдөлгөсөн шатны тоог хэвлэнэ. Түүний дараагийн мөрүүд дараах байдалтай байх ёстой:

Харригийн хөдөлгөөнүүд
Шатны хөдөлгөөнүүд
Харригийн хөдөлгөөнүүд
Шатны хөдөлгөөнүүд
...
Шатны хөдөлгөөнүүд
Харригийн хөдөлгөөнүүд

"Харригийн хөдөлгөөнүүд" гэдэг нь тэдний очсон давхрын жагсаалтыг дарааллын дагуу илэрхийлэх тоонууд. Энэ жагсаалт дахь элементийн тоо $10^{6}$-аас хэтрэх ёсгүй. Жагсаалтыг хэвлэхдээ эхлээд элементийн тоо, дараа нь зайгаар тусгаарлан элементүүдийг хэвлэнэ. Жагсаалтын эхний элемент $1$-ээс (Харригийн хайлтаа эхлүүлэх давхар) эхэлнэ. Эхнийхээс бусад жагсаалт тэг ширхэг элементтэй байж болно.

Харри зарим давхруудаар ахин явж өнгөрөх боломжтой бөгөөд бүх $n$ давхраар хамгийн багадаа нэг удаа очсон байх ёстойг санаарай. Харригийн шилжин өнгөрөх гэж буй хоёр давхар нь хоорондоо шатаар холбогдсон байх ёстой.

"Шатны хөдөлгөөнүүд" гэдэг нь шатнуудын шинэ байрлалыг тодорхойлсон утгуудаас тогтоно. (шатны дугаар, нэг үзүүрийн байрлал, нөгөө үзүүрийн байрлал). Шат бүр хамгийн ихдээ нэг л удаа хөдөлнө.

Олон боломжтой бол алийг нь ч хэвлэсэн болно.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
6 4
1 2
1 3
2 3
4 5
Гаралт
YES
2
3 1 2 3
2 3 5
3 5 4 5
4 5 6
3 6 5 3
Оролт
4 1
1 2
Гаралт
NO
Оролт
5 5
1 2
1 3
3 4
3 5
4 5
Гаралт
YES
0
6 1 2 1 3 4 5
Сэтгэгдлүүдийг ачааллаж байна...