- 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 ja : kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin .
Tämän jälkeen syötteessä on riviä, joista jokainen kuvaa yhden lentoyhteyden. Rivillä on kaksi kokonaislukua ja : 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
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.