#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");

int n, m, a, b, c, e, flux[1001][1001], viz[1001], t[1001], tot, muchii[1001];
vector<vector<int>> ad;

bool bfs(){
    queue<int> q;
    q.push(0);
    for (int i = 0; i < n + m + 2; ++i) {
        t[i] = 0;
    }
    for (int i = 0; i < n + m + 2; ++i) {
        viz[i] = 0;
    }
    viz[0] = 1;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = 0; i < ad[x].size(); ++i) {
            if (viz[ad[x][i]] == 0 && flux[x][ad[x][i]] > 0){
                t[ad[x][i]] = x;
                q.push(ad[x][i]);
                viz[ad[x][i]] = 1;
                if (ad[x][i] == n + m + 1)
                    return 1;
            }
        }
    }
    return 0;
}

int main() {
    fin>>n>>m>>e;
    ad.resize(n + m + 2);
    for (int i = 0; i < e; ++i) {
        fin>>a>>b;
        ad[a].push_back(n + b);
        ad[n + b].push_back(a);
        flux[a][n + b] = 1;
    }

    for (int i = 1; i < n + 1; ++i) {
        ad[0].push_back(i);
        ad[i].push_back(0);
        flux[0][i] = 1;
    }
    for (int i = n + 1; i < n + m + 1; ++i) {
        ad[i].push_back(n + m + 1);
        ad[n + m + 1].push_back(i);
        flux[i][n + m + 1] = 1;
    }

//    for (int i = 0; i < n + m + 2; ++i) {
//        cout<<i<<": ";
//        for (int j = 0; j < n + m + 2; ++j) {
//            cout<<flux[i][j]<<' ';
//        }
//        cout<<endl;
//    }

    while (bfs()){
//        for (int i = 0; i < n + m + 2; ++i) {
//            cout<<i<<": "<<viz[i]<<endl;
//        }
        for (int i = 0; i < ad[n + m + 1].size(); ++i) {
            if (viz[ad[n + m + 1][i]]){
                int minn = INT_MAX;
                int x = n + m + 1;
                while(x != 0){
                    cout<<t[x]<<' '<<x<<' '<<flux[t[x]][x]<<endl;
                    muchii[t[x]] = x - n;
                    minn = min(minn, flux[t[x]][x]);
                    x = t[x];
                }
                x = n + m + 1;
                while(x != 0){
                    flux[t[x]][x] = flux[t[x]][x] - minn;
                    flux[x][t[x]] = flux[x][t[x]] + minn;
                    x = t[x];
                }
//                for (int i = 0; i < n + m + 2; ++i) {
//                    cout<<i<<": ";
//                    for (int j = 0; j < n + m + 2; ++j) {
//                        cout<<flux[i][j]<<' ';
//                    }
//                    cout<<endl;
//                }
                tot = tot + minn;
                cout<<minn<<endl<<endl;
                break;
            }
        }
        cout<<"------------------------------------------------"<<endl;
    }
    fout<<tot<<endl;
//    for (int i = 0; i < ad.size(); ++i) {
//        cout<<i<<": ";
//        for (int j = 0; j < ad[i].size(); ++j) {
//            cout<<ad[i][j]<<' ';
//        }
//        cout<<endl;
//    }
    for (int i = 1; i < n + 1; ++i) {
        if (muchii[i] > 0)
            fout<<i<<' '<<muchii[i]<<endl;
    }
    return 0;
}