#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <set>
#include <queue>
#include <map>
#include <windows.h>
#include <iostream>
#include <windows.h>
#include <vector>
#include <algorithm>
#include <random>
#include <assert.h>
using namespace std;

int Random(int mi,int ma)
{
   std::mt19937 eng(rand()); // seed the generator
   std::uniform_int_distribution<> distr(mi, ma); // define the range
   return distr(eng);
}
struct muchie
{
    int a,b;
    muchie(int c,int d){a=c;b=d;};
    muchie(){};
    bool operator<(const muchie &comp) const
    {
        return comp.a!=a || comp.b!=b;
    }
};
struct date
{
    int L,R;
    vector<muchie> E;
};
date citeste(string in)
{
    date ret;
    int n;
    ifstream fin(in);
    fin>>ret.L;
    fin>>ret.R;
    fin>>n;
    for(int a=1;a<=n;a++)
    {
        muchie m;
        fin>>m.a>>m.b;
        ret.E.push_back(m);
    }
    return ret;
}
date genereaza()
{
    date ret;
    srand(GetTickCount());
    int L,R,nr;
    L=Random(1,10);
    R=Random(1,10);
    nr=Random(0, L*R);
//    L=Random(1,1000);
//    R=Random(1,1000);
//    nr=Random(0, min(1000,L*R));
    set<muchie> Es;
    for(int a=0;a<nr;a++)
        Es.insert(muchie(Random(1,L),Random(1,R)));
    ret.L=L;
    ret.R=R;
    ret.E=vector<muchie>(Es.begin(),Es.end());
    return ret;
}
///












map<int,int> Cuplaj;///   U=L=X,V=R=Y
map<int,unordered_set<int>> XY;
map<int,int> Adancime;

vector<int> Nesat;
bool BFS (int U)
{
    queue<int> Q;
    for(int a=1;a<=U;a++)
        if(Cuplaj[a]==0)
        {
            Adancime[a]=0;
            Q.push(a);///nesaturate
        }
        else
            Adancime[a]=-10;
    Adancime[0]=-10;
    while(Q.size())
    {
        int u=Q.front();Q.pop();
        if(Adancime[u]!=-10)
            for(auto v : XY[u])
                if(Adancime[Cuplaj[v]]==-10)
                {
                    Adancime[Cuplaj[v]]=Adancime[u]+1;
                    Q.push(Cuplaj[v]);
                }
    }
    return Adancime[0]!=-10;
}
bool DFS (int u)
{
    if (u == 0)return true;
    for(auto v : XY[u])
        if (Adancime[ Cuplaj[v] ] == Adancime[u] + 1)
            if (DFS(Cuplaj[v]))
            {
                Cuplaj[v] = u;
                Cuplaj[u] = v;
                return true;
            }
    Adancime[u] = -10;
    return false;
}
int cate;
void Afis(ostream &cout)
{
    cout<<"Cate: "<<cate<<endl;
    for(auto elem : Cuplaj)
        if(Cuplaj[elem.first]==elem.second && Cuplaj[elem.second]==elem.first && elem.first>0)
            cout << elem.first << " " << -elem.second << "\n";
}
int main()
{
    ///s=0
    ///<0 = Y = R = cele de jos din curs
    ///>0 = X = L = cele de sus din curs

    date d=citeste("cuplaj.in");
//    date d=genereaza();
//    cout<<"L="<<d.L<<endl;
//    cout<<"R="<<d.R<<endl;
//    cout<<"E="<<d.E.size();
//    for(int a=0;a<d.E.size();a++)
//        cout<<d.E[a].a<<" "<<d.E[a].b<<endl;
    for(int a=0;a<d.E.size();a++)
        XY[d.E[a].a].insert(-d.E[a].b);
    for(int a=-d.R;a<=d.L;a++)
        Cuplaj[a]=0;

    while(BFS(d.L))
        for(int a=1;a<=d.L;a++)
            if(Cuplaj[a]==0)
                if(DFS(a))
                    cate++;
    ofstream fout("cuplaj.out");
    Afis(fout);
}