CSES - Datatähti 2017 loppu - Tunnelit
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Pelaat peliä, joka muodostuu nn huoneesta ja mm 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 nn ja mm: huoneiden määrä ja tunnelien määrä. Huoneet on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, joista jokaisella on kaksi kokonaislukua aa ja bb. Tämä tarkoittaa, että huoneesta aa on tunneli huoneeseen bb.

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ä)

  • 1n101 \le n \le 10
  • 1m201 \le m \le 20

Osatehtävä 2 (31 pistettä)

  • 1n1001 \le n \le 100
  • 1m2001 \le m \le 200

Osatehtävä 3 (53 pistettä)

  • 1n1051 \le n \le 10^5
  • 1m21051 \le m \le 2 \cdot 10^5