Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Lentoreitit

Lentoreitit


View task | Model solution | Statistics


Lentoreitit

Time limit:1.00 s
Memory limit:128 MB

Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ lentoyhteyttä. Tavoitteena on, että mistä tahansa kaupungista pääsisi mihin tahansa toiseen kaupunkiin lentäen. Mikä on pienin määrä uusia yhteyksiä, joiden avulla tavoite onnistuu?

Syöte

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

Sitten syötteessä on $m$ riviä, jotka kuvaavat lentoyhteydet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$. Tämä tarkoittaa, että kaupungista $a$ on yhteys kaupunkiin $b$. Kaikki yhteydet ovat yksisuuntaisia.

Tuloste

Tulosta ensin kokonaisluku $k$: montako uutta yhteyttä tarvitaan.

Tulosta sitten $k$ riviä, joista jokainen kuvaa yhden uuden yhteyden. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat
Esimerkki

Syöte:
4 5
1 2
2 3
3 1
1 4
3 4


Tuloste:
1
4 2