D. Шагнал өгөх

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

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

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

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

R1 компаны ажилчид цагийг үргэлж хамт өнгөрүүлдэг: тэд хөл бөмбөг тоглож, хамт зуслан явж, уралдаан тэмцээн зохион байгуулдаг. Тэгэхээр энэ нь хэн нэг нь өөр хэн нэгэнд төлөх өртэй байх том биш юм.

Өнөөдөр бол мөнгөн шагнал өгөх өдөр. R1 компаний гүйцэтгэх захирал энэ сард мэрийж ажилласан хүн нэг бүрийг шагнахаар өөрийн өрөөндөө нэг нэгээр нь ажилчдыг урьсан байна. Гүйцэтгэх захирал хэн хэнд мөнгөний өртэйг мэддэг. Мөн тэр өөрийн өрөөндөө $x$ хүнийг шагнахаар уриад дараа нь тэр даруй $x$ хүнд тодорхой хэмжээний мөнгө зээлдүүлсэн $y$ хүнийг урьна, дараа нь тэд уулзаж болно гэдгийг ойлгож байгаа. Мэдээж хэрэг ийм нөхцөл байдалд түүний шинэ мөнгөн шагналыг авах $x$ хүний баяр баясгалан нь бага байх болно. Тиймээс R1 компаны гүйцэтгэх захирал ямар ч харилцаагүй ажилчдын хосыг тодорхойлсон байдлаар нэгийг нь дуудсаны дараа нөгөөг нь урих дарааллаар дуудахаар шийджээ.

Хэдий тийм ч компани маш олон ажилтантай бөгөөд гүйцэтгэх захиралд хангалттай цаг байхгүй. Тийм учраас энэ ажлыг танд даалгасан байна. Бүх ажилчдын хоорондын өрийн харилцаа өгөгдсөн, R1 компаний гүйцэтгэх захирал өөрийн өрөөндөө тэднийг дуудах дарааллыг тодорхойл, эсвэл тайлбарласан дараалал байхгүй гэдгийг тодорхойл.

Оролт

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

$p$, $q$ хос бүр нь оролтын өгөгдөлд хамгийн ихдээ нэг удаа байна гэдэг нь баталгаатай юм. Тухайлбал оролтын өгөгдөл $p$, $q$ ба $q$, $p$ хосуудыг нэгэн зэрэг агуулахгүй.

Гаралт

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

Хэрвээ олон зөв дараалал байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Орчуулсан: Даариймаа

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

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