CSES - Jalkapallo 2
  • Time limit: 2.00 s
  • Memory limit: 512 MB

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