E. Баавгай ба мартагдсан мод 2

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

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

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

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

Мод гэдэг нь $n$ орой болон $n - 1$ ирмэгээс тогтох холбоост чиглэлгүй граф юм.Оройнууд нь $1$-ээс $n$ хүртэл дугаарлагдсан байна.

Лимак бол жижиг туйлын баавгай. Тэрээр нэгэн удаа $n$ ширхэг оройтой модтой байсан боловч үүнийгээ алджээ.Гэхдээ тэрээр алдсан модныхоо талаар хэсэг зүйл санасаар байв.

Танд оройнуудын $m$ ширхэг хос $(a_{1}, b_{1}), (a_{2}, b_{2}), ..., (a_{m}, b_{m})$ өгөгдөнө.Лимак $i$ бүрийн хувьд $a_{i}$ болон $b_{i}$-ын хооронд ирмэг байхгүй байсан гэдгийг санаж байгаа юм.Тэрээр мөн $1$-дэх орой нь яг $k$ ширхэг ирмэгтэй холбогдсон байгааг санаж байв(үүний өнцөг нь $k$-тай тэнцүү байсан).

Лимак-ын санаж байгаа бүхэн нь зөв байх боломжтой юу? Өгөгдсөн нөхцөлийг хангах мод оршин байгаа эсэхийг тодорхойлно уу.

Оролт

Эхний мөрөнд харгалзан Лимак-ын модны оройны тоо, хориглогдсон хос оройнуудын тоо, $1$-дэх оройн өнцгийг илэрхийлэх 3-н бүхэл тоо $n$, $m$ болон $k$ () өгөгдөнө.

Дараагийн $m$ мөрийн $i$-дахь мөрөнд $i$-дахь хориглогдсон хос оройнуудыг илэрхийлэх 2 ялгаатай бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) өгөгдөнө.Оройнуудын хос бүр нь оролтод хамгийн ихдээ нэг удаа өгөгдөнө.

Гаралт

Өгөгдсөн нөхцөлийг хангах дор хаяж нэг ширхэг мод оршин байвал "possible" (хашилтгүйгээр) гэж хэвлэнэ.Бусад тохиолдолд, "impossible" (хашилтгүйгээр) гэж хэвлэнэ.

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

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

Оролт
5 4 2
1 2
2 3
4 2
4 1
Гаралт
possible
Оролт
6 5 3
1 2
1 3
1 4
1 5
1 6
Гаралт
impossible

Тэмдэглэл

Эхний жишээнд, $n = 5$ ширхэг орой байна.$1$-дэх оройн өнцөг нь $k = 2$ байх юм. $1 - 5$, $5 - 2$, $1 - 3$ болон $3 - 4$ гэсэн ирмэгүүдтэй модны хувьд бүх нөхцөлийг хангана.

2-дахь жишээнд, Лимак дараах ирмэгүүдийн аль нь ч байгаагүй гэж санаж байгаа: $1 - 2$, $1 - 3$, $1 - 4$, $1 - 5$ болон $1 - 6$.Иймд $1$-дэх орой нь бусад ямар ч оройтой холбогдож чадахгүй ба энэ нь ямар ч тохиромжтой мод байхгүй гэсэн утгатай болно.

Сэтгэгдлүүдийг ачааллаж байна...