CSES - 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

  • 1 \le n \le 10^5
  • 1 \le m \le 2 \cdot 10^5
  • 1 \le a,b \le n

Esimerkki

Syöte:

4 5
1 2
2 3
3 1
1 4
3 4

Tuloste:

1
4 2