D. Маргаан

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

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

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

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

Валерад $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг тоолуур байдаг. Тэдний зарим нь хоорондоо утсаар холбогдсон бөгөөд тоолуур тус бүрт тусгай товч байдаг.

Эхлээд бүх тоолуур $0$ тоог агуулсан байна. Та аль нэг тоолуур дээрх товчийг дарахад түүний утга нэгээр нэмэгдэнэ. Мөн түүнтэй утсаар шууд холбогдсон бүх тоолуурны дээр бичигдсэн утгууд нэгээр нэмэгдэнэ.

Валера, Игнат хоёр маргалдсан бөгөөд маргаан дараах байдлаар байна. Игнат $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоонуудын дарааллыг санасан байна. Валера ямар нэг ялгаатай тоолуурнуудын олонлог сонгох ёстой ба тэдгээр тоолуур бүр дээрх товчийг яг нэг удаа дарна (бусад тоолуур дээрх товчнууд дарагдаж болохгүй). Үүний дараа аль нэг $i$ дугаартай тоолуурны утга $a_{i}$ байвал Валера маргаанд ялагдана, эсрэг тохиолдоnд тэр ялна.

Валера маргаанд ялахын тулд аль тоолуурнуудын товчийг дарах хэрэгтэй болохыг тодорхойл.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $n$, $m$ $(1 ≤ n, m ≤ 10^{5})$ бүхэл тоонууд байна. Эдгээр нь Валерад байгаа тоолуурнуудын тоо болон утсаар холбогдсон тоолуурны хосын тоог илэрхийлнэ.

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

Сүүлийн мөрөнд $n$ ширхэг зайгаар тусгаарлагдсан $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ 10^{5})$ бүхэл тоонууд байх ба $a_{i}$ нь $i$-р тоолуурны хувьд Игнатын сонгосон утга юм.

Гаралт

Хэрвээ Валера маргаанд ялж чадахгүй бол нэг мөрөнд "-1" гэж хэвлэнэ.

Эсрэг тохиолдолд эхний мөрөнд $k$ $(0 ≤ k ≤ n)$ бүхэл тоог хэвлэнэ. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан ялгаатай $k$ ширхэг бүхэл тоонууд хэвлэнэ. Эдгээр нь Валера маргаанд ялахын тулд дарах ёстой товчнуудын дугаар бөгөөд дурын дарааллаар байна.

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

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

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

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