Šeštadieninė informatikos olimpiadininkų mokykla

Vilniaus mieste yra n sankryžų ir m jas jungiančių vienpusių kelių. Laimei, atstumai nedideli, ir per vieną dieną galima nuvažiuoti kur tik nori (jei tik yra tam tinkami keliai). Be to, kiekvieną vidurnaktį visų kelių kryptys apsikeičia!

Genadijus yra turistas, atvykęs iš Baltarusijos. Jis dar neapsisprendė, prie kurios sankryžos apsistoti. Jis nori apsistoti tokioje vietoje, kad galėtų iš jos nuvykti prie bet kurios kitos sankryžos. Deja, jis per mažai pasiskaitė apie Vilnių, ir bijo, kad čia gali būti įvesta komendanto valanda - taigi, naktį jis būti mieste nenori. Taigi, jis nori galėti nuvykti iki bet kurios sankryžos per vieną dieną (tačiau nebūtinai tą pačią dieną - jei Genadijus gali į vieną sankryžą nuvažiuoti pirmą dieną, o į kitą sankryžą - antrą dieną, tai laikome, kad jis į jas abi gali nuvažiuoti). Apie grįžimą atgal, deja, jis nepagalvojo, todėl nereikia rūpintis, ar jis spės tą pačią dieną grįžti atgal. Padėk Genadijui rasti sankryžas, prie kurių jis gali apsistoti, kad iki bet kurios kitos sankryžos galėtų nuvykti per vieną dieną.

Įvestis

Pirmojoje eilutėje bus pateikti du skaičiai ir () - sankryžų ir kelių skaičius. Kitose eilučių bus pateikta po du skaičius ir (), kurie nurodom kad keliu pirmą dieną galima nuvažiuoti iš sankryžos į sankryžą . Tarp dviejų sankryžų gali būti daug kelių, taip pat kelias gali vesti iš sankryžos į ją pačią.

Išvestis

Kiekvienai sankryžai išveskite vieną skaičių - , jei sankryža nėra tinkama apsistoti, ir , jei sankryža tinkama apsistoti.

4 4
1 2
1 3
2 4
3 4

1 0 0 1

5 5
1 2
2 3
3 4
4 2
5 4

0 1 1 1 0