A. NP-Хүнд бодлого

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

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

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

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

Саяхан Пари болон Аря NP-Хүнд бодлого-ын талаар хэсэг судалгаа явуулсан бөгөөд тэд хамгийн бага орой хучилтын бодлого нь ихээхэн сонирхолтой болохыг олж мэджээ.

$G$ граф өгөгдсөн гэж үзье. Уг графын оройнуудын дэд олонлог болох $A$ нь хэрэв уг графын $uv$ ирмэг бүрийн хувьд уг ирмэгийн ядаж нэг төгсгөлийн цэг нь $A$ дэд олонлогт байвал өөрөөр хэлбэл эсвэл (эсвэл 2-уулаа байж болно) байвал уг графын оройг хучиж байна гэж үзнэ.

Пари болон Аря нэгэн багийн тэмцээнд оролцон түрүүлсэн ба шагналд нь нэгэн чиглэлгүй гайхалтай граф авчээ. Одоо тэд уг графыг 2 хэсэг болгон хуваахыг хүсэж байгаа бөгөөд ингэхдээ тэдгээрийн тус бүр нь өөрийн авах хэсэг нь тухайн графын оройг хучиж байхыг хүсэж байгаа юм.

Тэд танд уг өөрсдийн графаа өгөхийг зөвшөөрсөн бөгөөд одоо та 2 ширхэг оройнуудын дэд олонлог болох $A$ болон $B$-г олох ёстой ба ингэхдээ эдгээр $A$ болон $B$ дэд олонлогууд нь 2-уулаа уг графын оройг хучиж байх ёстой ба эсвэл ингэх боломжгүй талаар мэдэгдэх юм. Түүнчлэн орой болгон нь нэгээс илүүгүй найзад очих юм (эсвэл та алинд нь ч өгөхгүй байж болох ба ингэснээр та тухайн оройг өөртөө үлдээнэ).

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 100 000$, $1 ≤ m ≤ 100 000$) өгөгдөх ба эдгээр нь харгалзан оройнуудын тоо болон шагналын графын ирмэгийн тоог илэрхийлнэ.

Дараагийн $m$ мөрийн мөр болгонд хос бүхэл тоо $u_{i}$ болон $v_{i}$ ($1  ≤  u_{i},  v_{i}  ≤  n$) өгөгдөх ба эдгээр нь $u_{i}$ болон $v_{i}$-ын хооронд чиглэлгүй ирмэг байгааг илэрхийлэх юм. Мөн граф нь ямар нэгэн өөртөө орсон гогцоо болон олон тооны ирмэг агуулаагүй байна.

Гаралт

Хэрэв уг графыг Пари болон Аря-д тэдгээрийн хүссэнээр хувааж өгөх боломжгүй бол "-1" (хашилтгүйгээр) гэж хэвлэнэ үү.

Хэрэв 2-уулаа графын оройг хучиж байх 2 ширхэг оройнуудын дэд олонлог оршин байвал тэдгээрийн тайлбарыг хэвлэнэ үү. Тайлбар болгон нь заавал 2 мөр агуулсан байна. Эхний мөрөнд тухайн дэд олонлог дотор байх оройнуудын тоог илэрхийлэх $k$ бүхэл тоог хэвлэх ба 2-дахь мөрөнд тэдгээр оройнуудын дугааруудыг илэрхийлэх $k$ ширхэг бүхэл тоонуудыг хэвлэнэ. $m ≥ 1$ учраас графыг хучиж буй эдгээр дэд олонлогууд нь хоосон байж болохгүйг анхаарна уу.

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

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

Оролт
4 2
1 2
2 3
Гаралт
1
2 
2
1 3 
Оролт
3 3
1 2
2 3
1 3
Гаралт
-1

Тэмдэглэл

Эхний жишээнд та $2$ дугаартай оройг Аря-д өгөх ба $1$ болон $3$ дугаартай оройнуудыг Пари-д өгөх бөгөөд $4$ дугаартай оройг өөртөө үлдээх юм (хэрвээ та хүсвэл хэн нэгэнд нь өгч болно).

2-дахь жишээнд Пари болон Аря-ын хүссэнээр хуваах ямар ч арга байхгүй байна.

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