Razporeditev
V skupini je $N$ zelo klepetavih otrok. Podanih je $M$ parov, ki med seboj radi klepetajo. Posamezen otrok lahko rad klepeta z več kot enim drugim otrokom. Napišite program, ki bo otroke razdelil v dve skupini tako, da noben par otrok, ki rad klepeta, ne bo v isti skupini, če je to mogoče.
Omejitve podatkov:
- $1 \leq N \leq 10^5$
- $ 1 \leq M \leq 10^6$
Vhodni in izhodni podatki:
Prva vrstica vsebuje število otrok $N$ (oštevilčimo jih z zaporednimi števili od 1 do $N$) in število klepetavih parov $M$. Sledi $M$ parov oblike $i$ $j$, kjer $i \neq j$ in $1 \leq i, j \leq N$, ki pomeni, da otroka $i$ in $j$ med sabo rada klepetata. Vsak par je naveden le enkrat.
Izhod naj bo zaporedje $N$ vrstic, kjer je v $i$-ti vrstici skupina $s_i$ (1 ali 2), ki ji pripada otrok $x_i$. Med vsemi veljavnimi rešitvami naj program izpiše leksikografsko najmanjšo (to je tista veljavna rešitev, v kateri ima prvi otrok čim manjšo številko skupine, če je še vedno več enakovrednih, izberemo tisto, kjer ima drugi otrok čim manjšo številko, itd.) Če razdelitev v skupine ni mogoča, naj se izpiše ena sama vrstica s številom -1.
Primer 1
Vhod:
8 7
1 2
1 4
2 3
4 3
1 5
1 6
7 8
Izhod:
1
2
1
2
2
2
1
2
Primer 2
Vhod:
8 8
1 2
1 4
2 3
4 3
2 5
1 5
1 6
7 8
Izhod:
-1