- Time limit: 1.00 s
- Memory limit: 512 MB
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$
- $1 \le n \le 100$
- $1 \le m \le 200$
- $1 \le n \le 10^5$
- $1 \le m \le 2 \cdot 10^5$