#include <bits/stdc++.h>
#include <iostream>

using namespace std;

ifstream in ("graf.in");
ofstream out ("graf.out");

//graf neorientat bipartit G = (V = (L, R), E). Un cuplaj în G este o submulţime de muchii M astfel încât pentru toate vârfurile v din V, există cel mult o muchie în M incidentă în v. Un cuplaj maxim este un cuplaj de cardinalitate maximă.
int n,m,e;//n cardinalul multimii e
int s, t;
int capacitati[10000][1000], flux[10000][10000];
// daca e capacitate pe x y inseama ca e arc orientat x y
int graf[10000][10000]; //graf rezidual
vector<int>adiacenta[10000];
vector<bool>vizitat;
int parinte[1000];//pt bfs


bool BFS()//returneaza true daca exista un nod de la sursa la destinatie
{
    vizitat.assign(n+m+1, false);
    int nod;

    queue <int> q;
    q.push(s);
    vizitat[s] = true;
    parinte[s] = -1;

    while(!q.empty())
    {
        //cat timp coada nu e vida vad daca gasesc un vecin pt nodul din fata cozii
        nod = q.front();
        q.pop();

        for(auto i:adiacenta[nod])//for(int i = 1; i <=n+m+1; i++)
        {
            if(!vizitat[i] && graf[nod][i] > 0)//daca mai pot folosi aceea muchie adica daca se mai poate adauga flux pe ea
            {
                vizitat[i] = true;
                parinte[i] = nod;
                q.push(i);

            }
        }

    }

    if(vizitat[t] == true)
        return true; //daca am vizitat si nodul destinatie inseamna ca am gasit drum de la sursa la el

    return false;

}


int FordFulkerson(int f)
{
    int x;
    int flux_max = f;

    while(BFS()) //se creste fluxul atat timp cat exista un drum de la sursa la destinatie
    {
        //cautam cea mai mica capacitate reziduala a drumului determinat de BFS

        int cap_reziduala = 10000;
        int i = t;

        while(i!=s)
        {
            x = parinte[i];
            if(cap_reziduala > graf[x][i])
            {
                cap_reziduala = graf[x][i];

            }

            i = parinte[i];


        }


        i = t;
        while(i!=s)
        {
            x = parinte[i];
            cout<<x<<" "<<i<<endl;
            graf[x][i] -=  cap_reziduala; //marim fluxul pt arcele directe in graful rezidual
            graf[i][x] +=  cap_reziduala; //scade fluxul pt arcele inverse in graful rezidual
            //e invers fata de graful normal
            flux[x][i] = 1;
             flux[i][x] = -1;
            i = parinte[i];



        }

        flux_max += cap_reziduala;


    }
return flux_max;

}



int main()
{
    in>>n>>m>>e;
    int x, y;
    s = 0;
    t = n+m+1;
    for(int i = 0 ;i < e; i++)
    {
        in>>x>>y;
        adiacenta[x].push_back(y+n);
        adiacenta[y+n].push_back(x);
        adiacenta[s].push_back(x);
        adiacenta[y+n].push_back(t);
        graf[x][y+n] = capacitati[x][y+n] =  1;
        graf[s][x] = capacitati[s][x] = 1;
        graf[y+n][t] = capacitati[y+n][t] = 1;


    }
   int flux_maxim = FordFulkerson(0);
    out<<"Cardinaliatatea cuplajului maxim este: "<<flux_maxim<<"\n";
/*
cout<<"GRAF REZIDUAL\n";
for(int i=1;i<=n;i++)
    {for(int j=n+1;j<=m+n;j++)
    cout<<graf[i][j]<<" ";
cout<<endl;}
cout<<"FLUX\n";
for(int i=1;i<=n;i++)
    {for(int j=n+1;j<=m+n;j++)
    cout<<flux[i][j]<<" ";
cout<<endl;}
*/

   for(int i = 1; i <=n; i++)
    {
        for(auto j:adiacenta[i])
        {

            if(j!=t && flux[i][j]==1)
            {
                out<<i<<" "<<j-n<<"\n";
            }
        }
    }

    return 0;
}