D. Цагираг зам 2

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

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

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

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

Бэрланд нь $i$ ба $i + 1$ ($1 ≤ i < n$), мѳн $n$ ба $1$ хотууд нь замаар холбогдсон Мѳнгѳн цагриг гэдэг замтай $n$ хоттойгоороо алдаршсан. Засгийн газар шинээр $m$ ширхэг зам барихаар шийдвэрлэв. Барихаар болсон замуудын жагсаалт бэлэн болсон байна. Зам бүр хоёр хотыг холбоно. Зам бүр цагригийн дотуур юмуу гадуур тавигдна. Шинэ замууд цагригтай огтлолцохгүй (замын тѳгсгѳлийн цэгээс бусад газар).

Бүтээн байгуулалтын загвар зохион бүтээгчид эдгээр замуудыг хоорондоо огтлолцдог хоёр зам байхгүй байхаар (замуудын тѳгсгѳлѳѳр огтлолцож болохыг тэмдэглэе) тѳлѳвлѳж болдог бол сэтгэл хангалуун байх болно. Хэрвээ үүнийг хийх боломжтой бол аль замуудыг цагриг дотуур, аль замуудыг цагригийн гадуур байлгах хэрэгтэй вэ?

Оролт

Эхний мѳрѳнд хоёр бүхэл тоо $n$, $m$ ($4 ≤ n ≤ 100$, $1 ≤ m ≤ 100$) ѳгѳгднѳ. Дараагийн $m$ мѳр бүрт $a_i$, $b_i$ ($1 ≤ a_i, b_i ≤ n$, $a_i ≠ b_i$) тоог агуулна. Нэгээс олон замаар холбогдох хоёр зам уг жагсаалтад байхгүй. Уг жагсаалт нь Мѳнгѳн цагирагийн аль ч замыг агуулахгүй.

Гаралт

Хэрвээ аль ч хоёр зам нь огтлолцохгүйгээр уг замуудыг тавьж болдоггүй бол Impossible гэж гарга. Бусад тохиолдолд $m$ ширхэг тэмдэгт хэвлэ. Тэмдэгт мѳрийн $i$-р үсэг нь жагсаалтын $i$-р замын хувьд цагригийн дотуур барих хэрэгтэй бол i, цагригийн гадуур барих хэрэгтэй бол o үсэг байна. Хэрвээ олон хариутай бол аль нэгийг нь гарга.

Орчуулсан: Sugardorj

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

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