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

Bittimaassa on nn kaupunkia, joiden välillä on mm tietä. Tavoitteena on rakentaa uusia teitä niin, että mistä tahansa kaupungista pääsee mihin tahansa kaupunkiin.

Tehtäväsi on selvittää, mikä on pienin mahdollinen määrä uusia teitä, joka riittää kaupunkien yhdistämiseen. Tulosta myös yksi tapa valita rakennettavat tiet.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua nn ja mm: kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu 1,2,,n1,2,\ldots,n.

Sitten syötteessä on mm riviä, joista jokainen kuvaa yhden tien. Rivillä on kaksi kokonaislukua aa ja bb: minkä kaupunkien välillä tie on.

Tie yhdistää aina kaksi eri kaupunkia, ja kahden kaupungin välillä on enintään yksi tie.

Tuloste

Ohjelmasi tulee tulostaa ensin kokonaisluku kk: montako tietä täytyy rakentaa.

Sitten ohjelmasi tulee tulostaa kk riviä, jotka kuvaavat uudet tiet. 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 2
1 2
3 4

Tuloste:

1
2 3