Codeforces Round #803 (Div. 2)
06:08:24 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
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