Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Lennot


Task | Statistics


CSES - LennotCSES - 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
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