E. Дима ба морьд

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

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

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

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

Дима морины ертөнцөд ирсэн байна. Энэ ертөнцөд $n$ ширхэг морьд амьдардаг ба морь бүрт хэд хэдэн дайсан (дайсагнал нь тэгш хэмтэй харилцаа юм) байдаг. Морины ертөнц нь тийм ч их дайсагналтай газар биш учраас морь бүрт хамгийн ихдээ $3$ дайсан байдаг.

Яг одоо морины ертөнцөд сонгуулийн кампанит ажил явагдаж байна. Димагаас морьдийг хоёр бүлэг болгон хувааж өгөхийг хүсчээ. Ингэхдээ дараах нөхцлийг хангасан байхыг хүсэж байгаа: бүлэгт нэгээс илүү дайсан морь байх ёсгүй.

Морьдыг хоёр бүлэг болгон хуваахад нь Димад туслана уу. Бүлгүүдийн аль нэг нь хоосон байхаар хувааж болно гэдгийг анхаараарай.

Оролт

Эхний мөрөнд $n, m$ $(1 \leq n \leq 3 \cdot 10^5; 0 \leq m \leq min(3 \cdot 10^5, \frac{n \cdot (n-1)}{2})$ гэсэн хоёр бүхэл тоо байна. Энэ нь нийт морины тоо болон дайсан хосуудын тоо юм.

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

Морьдыг $1$-ээс $n$ хүртэл дугаарласан ба морь бүр хамгийн ихдээ $3$ дайсантай байна. Дайсан хосууд оролтонд нэгээс олон удаа тохиолдохгүй.

Гаралт

$n$ ширхэг тэмдэгтүүдээс бүрдсэн нэг мөр хэвлэнэ. Хэрэв $i$ дугаартай морь нэгдүгээр бүлэгт ордог бол мөрийн $i$-р тэмдэгт "0" байх ёстой, эсрэг тохиолдолд "1" байна.

Хэрвээ шаардсан аргаар хуваах боломжгүй бол "-1" гэж хэвлэнэ.

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

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

Оролт
3 3
1 2
3 2
3 1
Гаралт
100
Оролт
2 1
2 1
Гаралт
00
Оролт
10 6
1 2
1 3
1 4
2 3
2 4
3 4
Гаралт
0110000000
Сэтгэгдлүүдийг ачааллаж байна...