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

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

Tiedossasi on mm 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 nn ja mm: oppilaiden määrä ja vaatimusten määrä. Oppilaat on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, joista jokaisella on kaksi kokonaislukua aa ja bb: oppilaat aa ja bb haluavat mennä samaan paikkaan.

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 0m1050 \le m \le 10^5
  • 1a,bn1 \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.