CSES - Kiertomatka
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Uolevi ja Maija aikovat tehdä kiertomatkan, jonka aikana he käyvät eri kaupungeissa ja liikkuvat niiden välillä lentokoneella.

Kiertomatka voi alkaa mistä tahansa kaupungista ja päättyä mihin tahansa kaupunkiin. Kaupungista toiseen voi siirtyä, jos tarvittava lentoyhteys on olemassa. Samassa kaupungissa voi käydä monta kertaa matkan aikana.

Tehtäväsi on suunnitella matka, johon kuuluu mahdollisimman monta eri kaupunkia.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja mm: kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Tämän jälkeen syötteessä on mm riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kaksi kokonaislukua aia_i ja bib_i: mistä kaupungista lento alkaa ja mihin se päättyy. Kaikki lennot ovat yksisuuntaisia.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: monessako eri kaupungissa Uolevi ja Maija voivat käydä matkansa aikana.

Rajat

  • 1n51041 \le n \le 5 \cdot 10^4
  • 1m51041 \le m \le 5 \cdot 10^4
  • 1ai,bin1 \le a_i, b_i \le n

Esimerkki

Syöte:

8 10
1 2
2 3
2 5
3 1
3 4
4 6
4 7
5 8
6 4
8 5

Tuloste:

6

Selitys: Mahdollinen reitti on 1->2->3->4->6->4->7.