Code Submission Evaluation System Login

BOI-leiri 2019

Repunpakkaus III


Task | Statistics


CSES - Repunpakkaus IIICSES - 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
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