- Time limit: 1.00 s
- Memory limit: 128 MB
Bittimaassa on kaupunkia, joiden välillä on 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 ja : kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin .
Sitten syötteessä on riviä, jotka kuvaavat lentoyhteydet. Jokaisella rivillä on kaksi kokonaislukua ja . Tämä tarkoittaa, että kaupungista on yhteys kaupunkiin . Kaikki yhteydet ovat yksisuuntaisia.
Tuloste
Tulosta ensin kokonaisluku : montako uutta yhteyttä tarvitaan.
Tulosta sitten 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