E. Бяцхан одой морь ба Зуны нарны баяр

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

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

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

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

Твайлайт Спаркл хорон санаат Найтмэйр Мүүн саран дээр мянган жил хоригдсоныхоо дараа ирж буй Зуны нарны баярын үеэр эргэн ирэх гэж байгааг мэдсэн. Тэр өөрийн удирдагч Гүнж Селестиад сануулах гэсэн боловч тэр тоогоогүй ба Твайлайтыг баярын бэлтгэлийг шалгуулахаар одой морьдын тосгонруу явуулсан.

Твайлайт Спаркл маань Найтмэйр Мүүний маршрутыг мөшгөхийг хүссэн. Харамсалтай нь тэр маршрутыг яг сайн мэдэхгүй. Түүний мэдэж байгаа зүйл нь Найтмэйр Мүүн зочилсон газар бүртээ очсон тоо нь тэгш үү эсвэл сондгой юу гэдгийг нь л мэдэж байна. Та Твайлайт Спарклд энэ мэдээлэлтэй нийцсэн дурын маршрутыг олоход туслаж чадах уу?

Одой морьдын тосгоныг өөртэйгөө холбогдсон оройгүй, давхар ирмэггүй, чиглэлгүй графаар дүрсэлж болно (оройнууд нь газар бол ирмэгүүд нь газруудын хоорондох зам байна). Найтмэйр Мүүний маршрут нь дурын газар эхлэж бас дуусч болно (энэ маршрут хоосон ч байж болно). Газар бүрт хэдэн ч удаа очиж болно. Маршрут нь $4n$-с их газар очсон байж болохгүй.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ ($2 ≤ n ≤ 10^{5}; 0 ≤ m ≤ 10^{5}$) байх ба Одой морьдын тосгон дахь газрууд болон замуудын тоо юм. Дараагийн $m$ мөр бүрт хоёр бүхэл тоо $u_{i}, v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i}$) байх ба эдгээр бүхэл тоонууд нь $u_{i}$ ба $v_{i}$ газруудын хооронд зам байгааг илэрхийлнэ.

Дараагийн мөрөнд $n$ бүхэл тоо $x_{1}, x_{2}, ..., x_{n}$ $(0 ≤ x_{i} ≤ 1)$ байх ба газар бүрт очсон тоо нь тэгш эсэхийг илэрхийлэх тоо байна. Хэрвээ $x_{i} = 0$ байвал $i$-р газарт тэгш удаа очсон байх ёстой бол бусад тохиолдолд сондгой удаа очсон байх ёстой.

Гаралт

Эхний мөрөнд очсон газруудын тоо $k$-г хэвлэ ($0 ≤ k ≤ 4n$). Тэгээд маршрутын дагуу газруудын дугаарыг илэрхийлэх $k$ бүхэл тоо хэвлэ. Хэрвээ $x_{i} = 0$ байвал маршрутад $i$-р газар тэгш удаа харагдах ёстой, бусад тохиолдолд сондгой удаа харагдах ёстой. Мэдээж өгөгдсөн замын систем нь өөртэйгөө холбогдсон газаргүй мөн маршрут дахь ямар ч хоёр хөрш газрууд ялгаатай байна.

Хэрвээ ямар ч маршрут шаардлагагүй бол $-1$-г хэвлэ. Хэрвээ хэд хэдэн шийдэл байвал та алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

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

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