Tunnelit |
| Time limit: | 1.00 s |
| Memory limit: | 512 MB |
|
Pelaat peliä, joka muodostuu $n$ huoneesta ja $m$ tunnelista. Jokainen tunneli on yksisuuntainen, eikä mistään huoneesta ole mahdollista päästä takaisin samaan huoneeseen tunneleita kulkemalla.
Jokaisessa tunnelissa on joukko kolikoita, jotka sinun tulee kerätä. Saat kerättyä kolikot kulkemalla tunnelin läpi. Kuitenkin kirouksen takia tunneli tuhoutuu tämän jälkeen etkä voi kulkea tunnelista uudestaan.
Peli muodostuu päivistä, ja jokaisen päivän alussa voit aloittaa mistä tahansa huoneesta ja kulkea tunneleiden kautta muihin huoneisiin. Mikä on pienin määrä päiviä, jotka tarvitset kerätäksesi kaikki kolikot tunneleista?
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: huoneiden määrä ja tunnelien määrä. Huoneet on numeroitu $1,2,\ldots,n$.
Sitten syötteessä on $m$ riviä, joista jokaisella on kaksi kokonaislukua $a$ ja $b$. Tämä tarkoittaa, että huoneesta $a$ on tunneli huoneeseen $b$.
Tuloste
Tulosta yksi kokonaisluku: pienin mahdollinen päivien määrä.
Esimerkki
Syöte:
6 7
2 1
2 5
3 2
5 1
5 4
6 2
6 3
Tuloste:
3
Osatehtävä 1 (16 pistettä)
- $1 \le n \le 10$
- $1 \le m \le 20$
Osatehtävä 2 (31 pistettä)
- $1 \le n \le 100$
- $1 \le m \le 200$
Osatehtävä 3 (53 pistettä)
- $1 \le n \le 10^5$
- $1 \le m \le 2 \cdot 10^5$
