#include <fstream>
#include <vector>
#include <iostream>
#include <string.h>
#include <string>
#include <sstream>
#include <climits>
#include <queue>

using namespace std;

int u, v, m, maxFlow;
int nodeCount;
vector<vector<int>> adjList;
vector<vector<int>> capacityMap;
vector<int> parentMap;
vector < pair<int, int> > result;

ifstream myIn("cuplaj.in");
ofstream myOut("cuplaj.out");

void ReadInputs() {
    myIn >> u >> v >> m;
    nodeCount = u + v + 2;


    adjList.resize(nodeCount, {});
    parentMap.resize(nodeCount, -1);
    capacityMap.resize(nodeCount, vector<int>(nodeCount, 0));


    for (int i = 1; i <= u; i++) {
        adjList[0].push_back(i);
        capacityMap[0][i] = 1;
    }
    for (int i = u + 1; i < nodeCount - 1; i++) {
        adjList[i].push_back(nodeCount - 1);
        capacityMap[i][nodeCount - 1] = 1;
    }

    int x, y;
    for (int i = 0; i < m; i++) {
        myIn >> x >> y; y = y + u;
        adjList[x].push_back(y);
        capacityMap[x][y] = 1;
    }

    for (int node = 0; node < nodeCount; node++) {
        if (node == nodeCount - 1) {
            cout << "f: ";
        }
        else if (node == 0) {
            cout << "s: ";
        }
        else if (node > u) {
            cout << node - u << ": ";
        }
        else {
            cout << node << ": ";
        }

        for (int i = 0; i < adjList[node].size(); i++) {
            int newNode = adjList[node][i];
            if (newNode == nodeCount - 1) {
                cout << "f ";
            }
            else if (newNode == 0) {
                cout << "s ";
            }
            else if (newNode > u) {
                cout << newNode - u << " ";
            }
            else {
                cout << newNode << " ";
            }
        }
        cout << "\n";
    }
    cout << "\n";
}

bool BFS() {
    fill(parentMap.begin(), parentMap.end(), -1);
    queue<int> q;
    q.push(0);

    while (not q.empty()) {
        int currentNode = q.front();
        q.pop();

        if (currentNode == nodeCount - 1) {
            return true;
        }

        for (const auto& nextNode : adjList[currentNode]) {
            int capacity = capacityMap[currentNode][nextNode];
            if ((parentMap[nextNode] == -1) && (capacity > 0)) {
                q.push(nextNode);
                parentMap[nextNode] = currentNode;
            }
        }
    }
    return false;
}

void EdmondsKarp() {
    while (BFS()) {
        for (int prevNode = nodeCount - 2; prevNode >= u + 1; prevNode--) {
            if (parentMap[prevNode] != -1) {
                parentMap[nodeCount - 1] = prevNode;
                int minFlow = INT_MAX;

                int nodeA = -1;
                int nodeB = -1;
                for (int node = (nodeCount - 1); node != 0; node = parentMap[node]) {
                    int prevNode = parentMap[node];
                    if (node != (nodeCount - 1))
                        if (nodeB == -1) {
                            nodeB = node - u;
                        }
                        else if (nodeA == -1) {
                            nodeA = node;
                        }

                    if (node == nodeCount - 1) {
                        cout << "f ";
                    }
                    else if (node == 0) {
                        cout << "s ";
                    }
                    else if (node > u) {
                        cout << node - u << ' ';
                    }
                    else {
                        cout << node << ' ';
                    }
                    minFlow = min(minFlow, capacityMap[prevNode][node]);
                }
                cout << '\n';
                if (minFlow <= 0) continue;

                result.push_back({ nodeA, nodeB });

                cout << "VALID\n";
                for (int node = (nodeCount - 1); node != 0; node = parentMap[node]) {
                    int prevNode = parentMap[node];
                    capacityMap[node][prevNode] += minFlow;
                    capacityMap[prevNode][node] -= minFlow;
                }
                cout << '\n';

                maxFlow += minFlow;
            }
        }
    }
}

void Output() {
    myOut << maxFlow << '\n';
    sort(result.begin(), result.end());
    for (int i = 0; i < result.size(); i++) {
        myOut << result[i].first << ' ' << result[i].second << '\n';
    }
}

int main() {
    ReadInputs();
    EdmondsKarp();
    Output();
}

/*
13
1 3
2 1
3 14
5 5
6 9 -- ISSUE MIHAI
6 16
7 7
8 6
10 8
11 2
15 4
17 10
20 15

13
1 3
2 1
3 14
5 5
13 9 -- ISSUE RAZVAN
6 16
7 7
8 6
10 8
11 2
15 4
17 10
20 15

*/