CSES - Luokkaretki
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Uolevin luokalla on n oppilasta. Luokka on lähdössä retkelle Helsinkiin niin, että osa oppilaista menee Korkeasaareen ja loput menevät Linnanmäelle.

Tiedossasi on m paria oppilaita, jotka vaativat päästä samaan paikkaan. Tehtäväsi on selvittää kaikki mahdollisuudet, moniko oppilas menee Korkeasaareen.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: oppilaiden määrä ja vaatimusten määrä. Oppilaat on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten syötteessä on m riviä, joista jokaisella on kaksi kokonaislukua a ja b: oppilaat a ja b haluavat mennä samaan paikkaan.

Tuloste

Tulosta n-pituinen bittijono, jonka bitti i on 1, jos i oppilasta voi lähteä Korkeasaareen, ja muuten 0.

Rajat

  • 1 \le n \le 10^5
  • 0 \le m \le 10^5
  • 1 \le a,b \le n

Esimerkki

Syöte:

5 3
1 2
2 3
1 5

Tuloste:

10011

Selitys: Korkeasaareen voi mennä 1, 4 tai 5 oppilasta.