Pelaat peliä, jossa on n luolaa ja niiden välillä m käytävää. Pelissä on örkkirotuja, jotka hallitsevat luolia. Peli on suunniteltu niin, että jos luolasta a pääsee luolaan b ja päinvastoin, sama rotu hallitsee luolia a ja b.

Tehtäväsi on selvittää, montako örkkirotua pelissä voi olla korkeintaan.

Syöte

Syötteen alussa on kaksi kokonaislukua n ja m: luolien määrä ja käytävien määrä. Luolat on numeroitu 1,2,\ldots,n.

Sitten syötteessä on m riviä, jotka kuvaavat käytävät. Jokaisella rivillä on kaksi kokonaislukua a ja b. Tämä tarkoittaa, että luolasta a on käytävä luolaan b. Kaikki käytävät ovat yksisuuntaisia.

Tuloste

Tulosta ensin kokonaisluku k: suurin mahdollinen örkkirotujen määrä.

Tulosta tämän jälkeen esimerkki siitä, mitkä örkkirodut hallitsevat luolia. Tulosta jokaiselle luolalle örkkirodun numero väliltä 1,2,\ldots,k. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

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

Esimerkki

Syöte:

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

Tuloste:

2
1 1 1 2 2