CSES - Lentoreitit
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Bittimaassa on nn kaupunkia, joiden välillä on mm 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 nn ja mm: kaupunkien määrä ja lentoyhteyksien määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

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

Tuloste

Tulosta ensin kokonaisluku kk: montako uutta yhteyttä tarvitaan.

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

Rajat

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

Esimerkki

Syöte:

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

Tuloste:

1
4 2