CSES - Örkit
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

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

Syöte

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

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

Tuloste

Tulosta ensin kokonaisluku kk: 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,,k1,2,\ldots,k. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5
  • 1a,bn1 \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