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

• $1 \le n,m \le 500$
• $1 \le k \le 1000$
• $1 \le a,b \le n$

Esimerkki

Syöte:

3 2 4
1 1
1 2
2 1
3 1

Tuloste:

2
1 2
3 1