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