Annettuna on suunnattu verkko, jossa ei ole syklejä. Tehtäväsi on laskea jokaiselle solmulle, moneenko solmuun siitä voi päästä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut $n$ ja $m$: solmujen määrä ja kaarten määrä. Solmut on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden kaaren. Kullakin rivillä on kaksi kokonaislukua $a$ ja $b$: solmusta $a$ on kaari solmuun $b$.

Tuloste

Tulosta $n$ lukua: moneenko solmuun mistäkin solmusta pääsee.

Rajat

• $1 \le n \le 5 \cdot 10^4$
• $1 \le m \le 10^5$

Esimerkki

Syöte:

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

Tuloste:

5 3 2 2 1