Kuten tiedämme aiemmasta tehtävästä, Syrjälän asukkaat pelaavat usein jalkapalloa keskenään. Peliä varten asukkaat pitää jakaa kahteen joukkueeseen, mutta joukkueisiin jakoa haittaa se, että jotkut Syrjälän asukkaista ovat riidoissa toisiensa kanssa. $m$ paria Syrjälän asukkaista on riidoissa keskenään. Tehtävänäsi on löytää sellainen joukkueisiin jako, että riitasuhteista korkeintaan $\frac{m}{2}$ on saman joukkueen sisällä.

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $m$, Syrjälän asukkaiden ja riitasuhteiden määrät. Seuraavalla $m$:llä rivillä on jokaisella kaksi lukua $a_i$ ja $b_i$, jotka tarkoittavat että asukkaat $a_i$ ja $b_i$ ovat riidoissa keskenään.

Tuloste

Tulosta merkkijono jossa on $n$ merkkiä. Kohdalla $i$ oleva merkki on 1 jos asukas $i$ kuuluu ensimmäiseen joukkueeseen ja 2 jos asukas $i$ kuuluu toiseen joukkueeseen.

Rajat

• $2 \le n \le 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $1 \le a_i, b_i \le n, a_i \neq b_i$

Tehtävässä on 50 testitapausta.

Esimerkki

Syöte:

5 6
1 5
1 2
3 4
2 3
4 1
1 3

Tuloste:

21122