CSES - Repunpakkaus III
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Uolevilla on n tavaraa joista jokainen painaa 1kg. Joillain tavaroilla on erityinen yhteys: on m tavaraparia niin että jos Uolevi pakkaa tavaran a_i niin Uolevin on pakattava myös tavara b_i, ja jos Uolevi pakkaa tavaran b_i niin Uolevin on pakattava myös tavara a_i.

Tehtäväsi on selvittää kaikki mahdolliset repun yhteispainot.

Syöte

Syötteen ensimmäisellä rivillä kaksi kokonaislukua n ja m: tavaroiden määrä ja erityiset tavaraparit.

Sitten syötteessä on m riviä joista jokaisella on luvut a_i ja b_i.

Tuloste

Tulosta n pituinen merkkijono jossa kohdalla i on 1 jos on mahdollista pakata tasan i kiloa reppuun ja 0 jos ei ole.

Rajat

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

Esimerkki

Syöte:

4 2
1 2
3 4

Tuloste:

0101

Syöte:

6 4
1 2
2 3
3 1
4 1

Tuloste:

110111