D. Төлөөлөгчид

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

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

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

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

Тринитарианы эзэн хаант улс яг $n = 3k$ ширхэг хотуудтай. Тэдгээр хотууд нь бүгд бүх эзэнт улсаар урсдаг Триссисипи голын эргүүд дээр байрладаг ажээ. Зарим хотууд нь уг голын нэг талд байрлах ба бусад бүх хотууд нь нөгөө талд байрладаг.

Зарим хотууд нь тэдгээрийн хооронд байх гүүрнүүдээр холбогдсон байв. Гүүр болгон нь голын эсрэг талуудад байрлах 2 хотыг холбодог. Аль ч 2 хотын хооронд нэгээс илүү гүүр оршин байхгүй.

Саяхан хаан болсон 3-р Тристан хотуудын дунд өөрийн төлөөлөгчдөө хуваарилаад завгүй байв. Нийтдээ $k$ ширхэг төлөөлөгч байх ба хаан тэдгээрийн тус болгоныг нь яг 3-н хотыг удирдаж байхаар томилохыг хүсжээ. Харамсалтай нь ямар ч төлөөлөгч гүүрээр холбогдсон хотуудыг удирдаж болохгүй. Учир нь тухайн төлөөлөгч гүүрээр дамжин өнгөрөх татварыг өөрийн халаасаа зузаатгахын тулд хэт өндөр байлгах ба энэ нь хааны нэр хүндэд муу юм.

Хэрэв боломжтой байвал 3-р Тристан хаанд туслан хотуудын хооронд эдгээр төлөөлөгчдийг хуваарилаж өгнө үү.

Оролт

Эхний мөрөнд хотуудын тоо болон гүүрнүүдийн тоог илэрхийлэх 2 бүхэл тоо $n$ болон $m$ ($3 ≤ n < 10^{5}$, $n = 3k$, $0 ≤ m ≤ 10^{5}$) өгөгдөнө. Дараагийн $m$ мөрөнд гүүрнүүдийг дүрсэлнэ. $i$-дахь мөрөнд 2 бүхэл тоо $a_{i}$ болон $b_{i}$ өгөгдөх ба эдгээр нь $i$-дахь гүүрээр холбогдож буй хотуудын дугаарыг илэрхийлнэ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$, $1 ≤ i ≤ m$).

Ямар ч гүүр нь нэг хотыг өөртэй нь холбохгүй ба ямар ч 2 хот нь нэгээс илүүгүй гүүрээр холбогдсон байна.

Гаралт

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

Бусад тохиолдолд эхний мөрөнд "$YES$" (хашилтгүйгээр) гэж хэвлэх ба 2-дахь мөрөнд хот бүрийн дарга нь аль төлөөлөгч байхыг хэвлэнэ. $i$-дахь тоо нь оролтод $i$ дугаартай өгөгдсөн (нийт $n$ ширхэг тоо өгөгдсөн) хотын дарга болох төлөөлөгчийн дугаарыг ($1$-ээс $k$ хүртэлх тоо байна) илэрхийлнэ.

Хэрэв олон тооны хариулт байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

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

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