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

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

Sinulle annetaan joukko vaatimuksia muotoa "kaupungista a tulee päästä kaupunkiin b 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 n ja m: kaupunkien määrä ja vaatimusten määrä. Kaupungit on numeroitu kokonaisluvuin 1,2,\dots,n.

Seuraavat m riviä kuvaavat vaatimukset. Jokaisella rivillä on kaksi kokonaislukua a ja b: kaupungista a tulee päästä kaupunkiin b.

Tuloste

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

Tulosta sitten k riviä, joista jokaisella on kaksi kokonaislukua a ja b: kaupungista a on yhteys kaupunkiin b.

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

Rajat

  • 1 \le n \le 2 \cdot 10^5
  • 0 \le m \le 5 \cdot 10^5
  • 1 \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