E. Сайн төлөвлөгөөгөөр Берландын замыг хучсан нь

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

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

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

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

Берланд $n$ хоттой ба тэдний зарим нь хос чиглэлтэй замаар холбогдсон. Бид зам бүрийн хувьд хатуу хучилттай эсэхийг нь мэдэж байгаа.

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

Харамсалтай нь бүх зүйл Хоёрдугаар Валерагийн хүссэн шиг гайхалтай биш.
Ажилчдын ихэнх нь гадаадын ажилчид буюу идэвхтэй хууль бус цагаачид байсан боловч Берланд хүний тавьсан шаардлагыг ойлгохдоо тийм ч сайн биш. Түүнчлэн нэг хотоос гарч буй замуудыг хатуу хучилттай болгох захиалга авсан ажилчид хотоос гарч буй хатуу хучилтгүй бүх замыг хатуу хучилттай болгосон ба эсрэгээрээ хатуу хучилттай замуудын хатуу хучилтыг хуулж авсан.

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

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n, m$ байх ба харгалзан Берланд дахь хотууд болон замуудын тоо юм. Дараагийн $m$ мөрөнд Берланд дахь замуудын тайлбар байна: $i$-р мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоон утга $a_{i}, b_{i}, c_{i}$ $(1 ≤ a_{i}, b_{i} ≤ n; a_{i} ≠ b_{i}; 0 ≤ c_{i} ≤ 1)$ байна. Эхний хоёр бүхэл тоон утга $(a_{i}, b_{i})$ нь $i$-р замаар холбогдсон хотуудын дугаарууд бол гуравдугаар бүхэл тоон утгын хувьд хэрвээ уг зам анх хатуу хучилттай байсан бол $(c_{i})$ нь 1 байна, бусад тохиолдолд 0 байна.

Берландын хотуудыг 1-с $n$ хүртэл харин замуудыг нь 1-с $m$ хүртэл дугаарлагдсан гэж үз. Берландын хоёр хотын хооронд нэгээс олон зам байхгүй.

Гаралт

Эхний мөрөнд бүх замыг хатуу хучилттай болгоход шаардлагатай өдрийн тоо $x$-г $(0 ≤ x ≤ n)$ хэвлэ. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $x$ ширхэг бүхэл тоон утгыг хэвлэх ба эдгээр нь ажилчдыг илгээх хотуудын дугаарууд байна. Хотуудын дугаарыг Валерагийн ажилчдыг илгээх дарааллаар хэвлэ. Хэрвээ хэд хэдэн шийдэл байвал алийг нь ч хэвлэж болно.

Хэрвээ бүх замыг хатуу хучилттай болгох ямар нэгэн зам байхгүй бол "$Impossible$" (хашилтгүйгээр) гэж хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

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