- 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