E. Дугуйчдын хот

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

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

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

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

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

Та уралдааныг мэргэжлийн болон анхан суралцагчдад 2-ууланд нь орж болохоор зохион байгуулахыг хүсэж байгаа. Тиймээс та уралдааныг 3-н төрөлд зохион байгуулна: амархан, дунд, хэцүү; оролцогч болгон тохирох төрөлдөө уралдана. Төрөл болгонд та маршрут сонгох шаардлагатай -- дараалан замаар холбогдсон уулзваруудын гинжин хэлхээ. Маршрут дараах шаардлагуудыг хангах ёстой:

  • бүх 3-н маршрут бүгд нэг уулзвараас эхлэх ёстой ба нэг уулзвар дээр дуусах ёстой (эхлэл болон төгсгөл нь нэг уулзвар байж болохгүй);
  • мөргөлдөхөөс сэргийлэхийн тулд аль ч 2 маршрут ижил уулзвартай байж болохгүй (эхлэл болон төгсгөлийн уулзварыг тооцохгүй), ба ижил замаар явж болохгүй (зам дээрх явах чиглэл үл хамааран болохгүй);
  • аль ч маршрут нэг уулзвараар 2 дамжих ёсгүй ба ижил замаар дахин явж болохгүй (зам дээр явах чиглэл үл хамааран болохгүй).

Тэмцээний бэлтгэл ажил удахгүй эхлэх гэж байгаа бөгөөд та уралдааны маршрутыг чадахаараа хурдан боловсруулах шаардлагатай байгаа. Энд маршрутын урт хамаарахгүй зөвхөн өгөгдсөн нөхцлүүд хангагдах ёстой.

Оролт

Эхний мөрөнд уулзварын тоо болон замын тоо болох 2 бүхэл тоонууд $n$, $m$ ($1 ≤ n, m ≤ 2*10^{5}$) өгөгдөнө.

Дараагийн $m$ ширхэг мөрний мөр болгон замын тайлбар бөгөөд холбож буй 2 уулзвар болох 2 бүхэл тоонууд агуулна. Эдгээр нь 1 дэхь замаас эхлэн дарааллаараа өгөгдсөн байна. Энд аль ч 2 уулзвар нэгээс олон замаар хоорондоо холбогдсон байх боломжгүй ба мөн уулзварыг өөртэй нь холбодог зам гэж байхгүй.

Энд зам ашиглан аль ч уулзвараас эхлэн аль ч уулзвар дээр очих боломжтой гэж хэлээгүй байгааг анхаарна уу.

Гаралт

Хэрвээ маршрутуудыг олох боломжтой бол эхний мөрөнд "$YES$" гэж хэвлэнэ үү. Дараагийн 3-н мөрөнд 3-н маршрутын тайлбарыг "$l$ $p_{1}$ ... $p_{l}$" хэлбэрээр хэвлэнэ үү. Энд $l$ нь маршрутад агуулагдах уулзварын тоо, $p_{1}, ..., p_{l}$ нь уулзваруудын дамжих дараалал. Маршрутууд дээрх нөхцлүүдийг заавал хангах ёстой.

Хэрвээ шаардагдсан нөхцлүүдийг хангахаар маршрутуудыг зохиох боломжгүй бол $NO$ гэж хэвлэнэ үү.

Орчуулсан: Энхлут

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

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