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