- Time limit: 1.00 s
- Memory limit: 512 MB
Bittimaassa on kaupunkia, joista jokaisessa on lentokenttä. Mitään lentoyhteyksiä ei ole kuitenkaan vielä olemassa.
Sinulle annetaan joukko vaatimuksia muotoa "kaupungista tulee päästä kaupunkiin 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 ja : kaupunkien määrä ja vaatimusten määrä. Kaupungit on numeroitu kokonaisluvuin .
Seuraavat riviä kuvaavat vaatimukset. Jokaisella rivillä on kaksi kokonaislukua ja : kaupungista tulee päästä kaupunkiin .
Tuloste
Tulosta ensin kokonaisluku : tarvittava yhteyksien määrä.
Tulosta sitten riviä, joista jokaisella on kaksi kokonaislukua ja : kaupungista on yhteys kaupunkiin .
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