Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Tanssiaiset


Task | Statistics


CSES - TanssiaisetCSES - Tanssiaiset

Time limit:1.00 s Memory limit:512 MB

Koulussa on $n$ poikaa ja $m$ tyttöä. Ensi viikolla järjestetään tanssiaiset, joissa jokaisessa tanssiparissa on poika ja tyttö. Tiedossasi on $k$ mahdollista paria, jotka suostuvat tanssimaan keskenään.

Tehtäväsi on selvittää suurin mahdollinen tanssiparien määrä sekä näyttää, miten tämän määrän voi saavuttaa.

Syöte

Syötteen ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $k$: poikien, tyttöjen sekä mahdollisten parien määrä. Pojat on numeroitu $1,2,\dots,n$, ja tytöt on numeroitu $1,2,\dots,m$.

Tämän jälkeen syötteessä on $k$ riviä, jotka kuvaavat mahdolliset parit. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: poika $a$ ja tyttö $b$ suostuvat tanssimaan keskenään.

Tuloste

Tulosta ensin yksi kokonaisluku $r$: suurin mahdollinen tanssiparien määrä. Tulosta tämän jälkeen $r$ riviä, jotka kuvaavat parit. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat
Esimerkki

Syöte:
3 2 4
1 1
1 2
2 1
3 1


Tuloste:
2
1 2
3 1