CSES - Lennot
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Bittimaassa on nn kaupunkia, joista jokaisessa on lentokenttä. Mitään lentoyhteyksiä ei ole kuitenkaan vielä olemassa.

Sinulle annetaan joukko vaatimuksia muotoa "kaupungista aa tulee päästä kaupunkiin bb lentäen". Tehtäväsi on perustaa joukko yksisuuntaisia lentoyhteyksiä, jotka toteuttavat kaikki vaatimukset.

Mikä on pienin tarvittava määrä lentoyhteyksiä? Entä miten yhteydet voi valita käytännössä?

Syöte

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

Seuraavat mm riviä kuvaavat vaatimukset. Jokaisella rivillä on kaksi kokonaislukua aa ja bb: kaupungista aa tulee päästä kaupunkiin bb.

Tuloste

Tulosta ensin kokonaisluku kk: tarvittava yhteyksien määrä.

Tulosta sitten kk riviä, joista jokaisella on kaksi kokonaislukua aa ja bb: kaupungista aa on yhteys kaupunkiin bb.

Voit tulostaa minkä tahansa kelvollisen ratkaisun, kunhan yhteyksien määrä on pienin mahdollinen.

Rajat

  • 1n21051 \le n \le 2 \cdot 10^5
  • 0m51050 \le m \le 5 \cdot 10^5
  • 1a,bn1 \le a,b \le n

Esimerkki

Syöte:

4 6
1 3
1 4
2 3
2 4
3 1
3 2

Tuloste:

4
1 2
2 3
3 1
3 4