#include <bits/stdc++.h>

using namespace std;

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

class Graph
{
private:

    int verticesNo;
    int edgesNo;
    int oriented;      //0/1/3(for unoriented with weights)/4(for oriented with weights/5 for reading adjacency matrix/6 for multigraph/7 for oriented with weights adjlist
    //-----------------------------------------|
    vector<vector<int> > adjacencyList;//       |
    vector<vector<pair<int,int> > > weights;//   |->should be compressed in a single way of storing both weighted and simple graphs
    vector<tuple<int,int,int> > edges;//        |
    vector<vector<int> >matrix;//
    //-----------------------------------------|


    void dfs(int vertex, vector<int> &visited);                         //simple dfs
    void dfsScc(int vertex, vector<int> &visited, vector<int> &scc);    //dfs for storing strongly connected components
    void dfsWstack(int vertex, vector<int> &visited, stack<int> &st);   //dfs with a stack for both topological sorting and strongly connected components
    void dfsWMaxDistance(int vertex, int distance,vector<int> &visited, int &maxDistance,  int &furthestVertex);
    int minWeightVertex(vector<int> &helper, vector<int> &includeInMst);         //pretty efficently choosing the vertex with min weight
    void checkForCycle(int vertex);
    int edgeForEuler(int vertex1, int vertex2);
    void unlinkEdge(int vertex1, int vertex2);
    int countingDFS(int vertex, vector<int> &visited);
    int matchingDFS(int vertex, vector<int> &visited, vector<int> &left, vector<int> &right);


public:

    Graph();
    Graph(int verticesNo, int edgesNo);                                 //only for transposing a graph
    Graph(int verticesNo, int edgesNo, int oriented);
    Graph transpose();

    void bfs(int start);                                                //BFS

    void stronglyConnectedComponents();

    int connectedComponentsNo();

    void topologicalSort();

    void HH();

    void MST();

    void BF(int start);

    void royFloyd();

    int treeDiameter();

    int isConnected();

    int isEulerian();

    void eulerianCycle();

    void dijkstra(int start);

    void matching(int semigraph1, int semigraph2);

    virtual ~Graph();

};
Graph::Graph()
{
    verticesNo = edgesNo = oriented = 0;
    this->adjacencyList.clear();
    this->weights.clear();
}
Graph::Graph(int verticesNo, int edgesNo)
{
    this->verticesNo = verticesNo;
    this->edgesNo = edgesNo;
    this->adjacencyList.resize(verticesNo+1);
}
Graph::Graph(int verticesNo, int edgesNo, int oriented)
{
    this->verticesNo = verticesNo;
    this->edgesNo = edgesNo;
    this->oriented = oriented;


    if(oriented < 2)
    {this->adjacencyList.resize(verticesNo + 1);
    int vertex1, vertex2;
    for(int i = 0; i < this->edgesNo; i++)
    {
        fin>>vertex1>>vertex2;
        this->adjacencyList[vertex1].push_back(vertex2);
        if(this->oriented == 0)
            this->adjacencyList[vertex2].push_back(vertex1);
    }
    }
    else if( oriented == 4)
    {
        this->edges.resize(edgesNo+1);
        int vertex1,vertex2,cost;
        tuple<int,int,int> temp;
        for(int i = 0; i <this->edgesNo; i++)
        {
            fin>>vertex1>>vertex2>>cost;
            temp = make_tuple(vertex1,vertex2,cost);
            edges[i] = temp;

        }

    }
    else if(oriented == 5)
    {
        int temp;
        this->matrix.resize((this->verticesNo +1) * (this->verticesNo+1));

        for(int i = 0; i < verticesNo; i++)
            for(int j = 0; j < verticesNo; j++)
                {

                    fin>>temp;
                    matrix[i].push_back(temp);
                }



    }
    else if(oriented == 6)
    {
        this->adjacencyList.resize(verticesNo+1);
        int vertex1,vertex2;

        for(int  i = 1; i <= edgesNo; i++)
        {
            fin>>vertex1>>vertex2;

            adjacencyList[vertex1].push_back(vertex2);
            adjacencyList[vertex2].push_back(vertex1);

        }

    }
    else
    {
        this->adjacencyList.resize(verticesNo + 1);
        this->weights.resize(verticesNo+1);
        int vertex1, vertex2, cost;
        pair<int,int> temp;
        for(int i = 0; i < this->edgesNo; i++)
        {
            fin>>vertex1>>vertex2>>cost;

            temp.first = vertex2;
            temp.second = cost;


            this->weights[vertex1].push_back(temp);

            if(oriented == 3)
            {
                temp.first = vertex1;
                this->weights[vertex2].push_back(temp);
            }
        }


    }

}
Graph::~Graph()
{
        this->adjacencyList.clear();
        this->weights.clear();
}
void Graph::bfs(int start)
{
    int n = this->verticesNo;
    vector<int> visited;
    vector<int> distances;
    queue<int> order;
    order.push(start);

    for(int i = 0; i <= n; i++)
    {
        visited.push_back(0);
        distances.push_back(-1);
    }
    distances[start] = 0;
    visited[start] = 1;

    while(!order.empty())
    {
        int current = order.front();
        int sz = adjacencyList[current].size();

        order.pop();

        for(int i = 0; i < sz; i++)
        {
            int temp = adjacencyList[current][i];

            if(visited[temp] == 0)
            {
                visited[temp] = 1;
                order.push(temp);
                distances[temp] = distances[current]+1;
            }
        }

    }

    for(int i = 1; i < distances.size(); i++)
        fout<<distances[i]<<" ";

}
void Graph::dfs(int vertex, vector<int> &visited)
{
    visited[vertex] = 1;

    int sz = adjacencyList[vertex].size();

    for(int i = 0; i < sz; i++)
    {
        if(visited[adjacencyList[vertex][i]] == 0)
            dfs(adjacencyList[vertex][i],visited);
    }
}
void Graph::dfsScc(int vertex, vector<int> &visited, vector<int> &scc)
{
    visited[vertex] = 1;
    scc.push_back(vertex);

    int sz = adjacencyList[vertex].size();

    for(int i = 0; i < sz; i++)
    {
        if(visited[adjacencyList[vertex][i]] == 0)
            dfsScc(adjacencyList[vertex][i],visited, scc);
    }
}
int Graph::connectedComponentsNo()
{

    vector<int> visited;
    int ccn = 0; //no of connected components

    for(int i = 0 ; i <= this->verticesNo; i++)
        visited.push_back(0);

    for(int i = 0; i <= this->verticesNo; i++)
        if(visited[i] == 0)
        {
            dfs(i,visited);
            ccn++;
        }


    return ccn;

}
void Graph::stronglyConnectedComponents()
{
    stack<int> st;

    vector<int> visited;
    vector<vector<int>> sccs;
    vector<int> tempScc;

    int sccn = 0;
    for(int i = 0; i <= verticesNo; i++)
    {
        visited.push_back(0);
    }

    for(int i = 1; i <= verticesNo; i++)
        if(visited[i] == 0)
            dfsWstack(i,visited,st);

    Graph tg = transpose();

    for(int i = 0; i <= verticesNo; i++)
        visited[i] = 0;

    while(!st.empty())
    {
        int temp = st.top();
        st.pop();

        if(visited[temp] == 0)
        {   tempScc.clear();
            tg.dfsScc(temp,visited, tempScc);
            sccn++;
            sccs.push_back(tempScc);
        }
    }
    fout<<sccn<<endl;

    for(int i = 0 ; i < sccs.size(); i++)
    {
        int sz = sccs[i].size();
        for(int j = 0; j < sz; j++)
            fout<<sccs[i][j]<<" ";
            fout<<"\n";

    }


}
void Graph::dfsWstack(int vertex, vector<int> &visited, stack<int> &st)
{
    visited[vertex] = 1;

    int sz = adjacencyList[vertex].size();

    for(int i = 0; i < sz; i++)
    {
        if(visited[adjacencyList[vertex][i]] == 0)
            dfsWstack(adjacencyList[vertex][i],visited,st);
    }

    st.push(vertex);

}
void Graph::topologicalSort()
{
    stack<int> st;

    vector<int> visited;

    for(int i = 0; i <= this->verticesNo; i++)
        visited.push_back(0);

    for(int i = 1 ; i <=this->verticesNo; i++)
        if(visited[i] == 0)
            {dfsWstack(i,visited,st);}

    while(!st.empty())
    {
        fout<<st.top()<<" ";
        st.pop();
    }

}
void Graph::HH()
{

    int n,temp;
    vector<int> seq;
    fin>>n;
    for(int i = 0; i < n; i++)
    {
        fin>>temp;
        seq.push_back(temp);
    }

    while(true)
    {
        sort(seq.begin(),seq.end());
        int sz = seq.size()-1;
        if(seq[sz] == 0)
        {
            cout<<1;
            return;
        }

        int v = seq[sz];
        seq.pop_back();

        if(v > seq.size())
        {
            cout<<0;
            return;
        }

        for(int i = v-1; i >=0; i--)
        {
            seq[i]--;
            if(seq[i] < 0)
            {
                cout<<0;
                return;
            }

        }
    }


}
Graph Graph::transpose()
{
    Graph transposedGraph(verticesNo, edgesNo);

    for(int v = 1; v <= verticesNo; v++)
    {
        int sz = adjacencyList[v].size();

       for(int i = 0; i < sz; i++)
        {
            transposedGraph.adjacencyList[this->adjacencyList[v][i]].push_back(v);
        }

    }


    return transposedGraph;

}
int Graph::minWeightVertex(vector<int> &helper, vector<int> &includeInMst)
{
    int minimum, indexOfMin;
    minimum  = INT_MAX;

    for(int i = 1; i <= verticesNo; i++)
        if(includeInMst[i] == 0 && helper[i] < minimum)
        {
            minimum = helper[i];
            indexOfMin = i;
        }

    return indexOfMin;
}
void Graph::MST()
{
    vector<int> mst;            //used for storing the MST the vertex with the lowest weight from includeInMst
    vector<int> includeInMst;        //vertices that are included in MST
    vector<int> helper;         //the smallest weights to go from current vertex to any other vertex
                                //updated every step

    for(int i = 0 ; i <= verticesNo; i++)
    {
        helper.push_back(INT_MAX);
        includeInMst.push_back(0);
        mst.push_back(NULL);
    }

    helper[1] = 0;
    mst[1] = -1;
    for(int i = 1 ; i <= verticesNo; i++)
    {
        int nextVertex = minWeightVertex(helper, includeInMst);  //we get the least weighted edge
        includeInMst[nextVertex] = 1;

        int sz = weights[nextVertex].size();//-----------------------
        //cout<<nextVertex<<"--"<<sz<<endl;
        for(int j = 0; j < sz; j++)
        {   int temp1 = weights[nextVertex][j].first;
            int temp2 = weights[nextVertex][j].second;

            if(includeInMst[temp1] == 0 && temp2 < helper[temp1])
            {
                mst[temp1] = nextVertex;
                helper[temp1] = temp2;
            //cout<<helper[weights[nextVertex][j].first];
                //cout<<endl;
            }

        }

    }
    int sum = 0;
    for(int  i = 2; i <= verticesNo; i++)
        sum+= helper[i];



    fout<<sum<<"\n";
    fout<<verticesNo - 1<<"\n";
    for(int  i = 2; i <= verticesNo; i++)
        fout<<mst[i]<<" "<<i<<"\n";

}
void Graph::BF(int start)
{
     vector<int> distances;
    for(int  i = 0; i <= verticesNo; i++)
        distances.push_back(INT_MAX);
     vector<int> checked;
     for(int  i = 0; i <= verticesNo; i++)
        checked.push_back(0);
     vector<int> inqueue;
     for(int  i = 0; i <= verticesNo; i++)
        inqueue.push_back(0);

     queue<int> q;
     q.push(start);
     inqueue[start] = 1;

    distances[start] = 0;


    while(!q.empty())
    {
        int current = q.front();
        checked[current]++;

        if(checked[current] >= this->verticesNo)
        {
            fout<<"Ciclu negativ!";
            return;
        }
        q.pop();
        inqueue[current] = 0;

        int sz = weights[current].size();
        for(int i = 0; i <sz; i++)
        {
            int adjV = weights[current][i].first;
            int weight = weights[current][i].second;

            if(distances[adjV] > distances[current] + weight)
            {
                distances[adjV] = distances[current] + weight;

                if(inqueue[adjV] == 0)
                    q.push(adjV);
            }
        }

    }

    for(int i = 2; i <= this->verticesNo; i++)
        fout<<distances[i]<<" ";

}
void Graph::royFloyd()
{

	int i, j, k;
	for (i = 0; i < this->verticesNo; i++)
		for (j = 0; j < this->verticesNo; j++)
			for (k = 0; k < this->verticesNo; k++)
				if (matrix[j][i] && matrix[i][k] && (matrix[j][k] > matrix[j][i] + matrix[i][k] || !matrix[j][k]) && j != k)
                    matrix[j][k] = matrix[j][i] + matrix[i][k];



    for(int i = 0; i < verticesNo; i++)
        {
            for(int j = 0; j < verticesNo; j++)
                    fout<<matrix[i][j]<<" ";
            fout<<"\n";
        }
}
void Graph::dfsWMaxDistance(int vertex,  int distance,vector<int> &visited, int &maxDistance, int &furthestVertex)
{
    visited[vertex] = 1;
    distance++;

    int sz = adjacencyList[vertex].size();

    for(int i = 0; i < sz; i++)
{
        if(visited[adjacencyList[vertex][i]] == 0)
        {
            if(distance >= maxDistance)
            {
                maxDistance = distance;
                furthestVertex = adjacencyList[vertex][i];
            }
            dfsWMaxDistance(adjacencyList[vertex][i],distance, visited, maxDistance, furthestVertex);
        }
    }
}
int Graph::treeDiameter()
{
    vector<int> visited1;
    int distance = 0;
    for(int i = 0; i < this->verticesNo; i++)
        visited1.push_back(0);
    int maxDistance = INT_MIN;
    int furthestVertex = 0;

    dfsWMaxDistance(1,distance + 1, visited1, maxDistance, furthestVertex);

    vector<int> visited2;
    distance = 0;
    for(int i = 0; i < this->verticesNo; i++)
        visited2.push_back(0);

    dfsWMaxDistance(furthestVertex, distance + 1,visited2, maxDistance,furthestVertex );
    return maxDistance;
}
void Graph::eulerianCycle()
{
    int vertex = 0;
    for(int i = 1; i <=verticesNo+1; i++)
    {
        if(adjacencyList[i].size() % 2 == 0)//searching for a vertex with odd degree
        {
            vertex = i;
            break;
        }
    }

    checkForCycle(vertex);

}
void Graph::checkForCycle(int vertex)
{
    int sz = adjacencyList[vertex].size();
    for(int i = 0; i < sz; i++)
    {
        int temp = adjacencyList[vertex][i];


        if(temp != -1 && edgeForEuler(vertex, temp) != 0)
        {
                fout<<vertex<<" ";
                unlinkEdge(vertex, temp);
                checkForCycle(temp);
        }
    }

}
int Graph::edgeForEuler(int vertex1, int vertex2)
{
    int counter = 0;
    int sz = adjacencyList[vertex1].size();
    vector<int> visited;
    for(int i = 0 ; i <= this->verticesNo+1; i++)
    {
        visited.push_back(0);
    }

    for(int i = 0 ; i < sz; i++)
    {
        if(adjacencyList[vertex1][i] != -1)
        {
            counter++;
        }
    }

    if(counter == 1)  //if there's only one adjacent vertex to vertex1
        return 1;

    int counter1 = countingDFS(vertex1, visited);
    unlinkEdge(vertex1, vertex2);

    visited.clear();
    for(int i = 0 ; i <= this->verticesNo+1; i++)
    {
        visited.push_back(0);
    }

    int counter2 = countingDFS(vertex1,visited);
    adjacencyList[vertex1].push_back(vertex2);
    adjacencyList[vertex2].push_back(vertex1);



    if(counter1 > counter2)
        return 0;
    else
        return 1;

}
void Graph::unlinkEdge(int vertex1, int vertex2)
{
    auto index1 = find(adjacencyList[vertex1].begin(),adjacencyList[vertex1].end(),vertex2);
    *index1 = -1;
    auto index2 = find(adjacencyList[vertex2].begin(),adjacencyList[vertex2].end(),vertex1);
    *index2 = -1;
}
int Graph::countingDFS(int vertex, vector<int> &visited)
{
    visited[vertex] = 1;
    int counter = 1;

    int sz = adjacencyList[vertex].size();
    for(int i = 0 ; i< sz; i++)
    {
        if(adjacencyList[vertex][i] != -1 && visited[adjacencyList[vertex][i]] ==0)
        {
            counter += countingDFS(adjacencyList[vertex][i], visited);
        }
    }
    return counter;
}
int Graph::isEulerian()
{
   if(!isConnected())
        return 0;
   int counter = 0;
   for(int i = 1; i<=this->verticesNo; i++)
   {
       if(adjacencyList[i].size() & 1)
        counter++;
   }

   if(counter > 2)
    return 0;

   return 1;
}
int Graph::isConnected()
{

    vector<int> visited;

    for(int i = 0 ;i <= this->verticesNo; i++)
    {
        visited.push_back(0);
    }
    int i;
    for(i = 1; i <= this->verticesNo; i++)
    {
        if(adjacencyList[i].size() !=0)
            break;
    }

    if(i == this->verticesNo)
    {
        return 1;
    }

    dfs(i, visited);

    for(i = 1; i<= this->verticesNo; i++)
    {
        if(visited[i] == 0 && adjacencyList[i].size() != 0)
            return 0;

    }
    return 1;


}
void Graph::dijkstra(int start)
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    vector<int> distances;
    for(int i = 0; i <= this->verticesNo; i++)
    {
        distances.push_back(INT_MAX);
    }


    int temp = 0;
    pq.push(make_pair(temp,start));
    distances[start] = 0;

    while(!pq.empty())
    {
        int current = pq.top().second;
        pq.pop();

        int sz = weights[current].size();

        for(int i = 0 ; i < sz; i++ )
        {
            int adjacent = weights[current][i].first;
            int weight = weights[current][i].second;

            if(distances[current] + weight < distances[adjacent])
            {
                distances[adjacent] = distances[current] + weight;
                pq.push(make_pair(distances[adjacent], adjacent));
            }
        }


    }

    for(int i = 2; i <= this->verticesNo; i++)
    {

        if(distances[i] != INT_MAX)
            fout<< distances[i]<<" ";
        else fout<<0<<" ";

    }

}
int Graph::matchingDFS(int vertex, vector<int> &visited, vector<int> &left, vector<int> &right)
{
    if(visited[vertex] == 1)
        return 0;
    visited[vertex] = 1;

    int sz = adjacencyList[vertex].size();

    for(int i = 0; i < sz; i++)
    {
        if(right[adjacencyList[vertex][i]] == 0)
        {
            left[vertex] = adjacencyList[vertex][i];
            right[adjacencyList[vertex][i]] = vertex;


            return 1;
        }
    }

    for(int i = 0; i < sz; i++)
    {
        if(matchingDFS(right[adjacencyList[vertex][i]], visited, left, right) == 1)
        {
            left[vertex] = adjacencyList[vertex][i];

            right[adjacencyList[vertex][i]] = vertex;

            return 1;
        }
    }

    return 0;


}

void Graph::matching(int semigraph1, int semigraph2)
{
    int maxmatches = 0;
    vector<int> visited(this->verticesNo +1, 0);
    vector<int> left(this->verticesNo+1);
    vector<int> right(this->verticesNo+1);

    int temp = 1;
    while(temp)
    {
        temp = 0;
        visited.assign(visited.size(), 0);
        for(int i = 1; i<= semigraph1; i++)
        {
            if(left[i] == 0 && matchingDFS(i,visited,left,right) == 1)
            {
                maxmatches++;
                temp = 1;
            }
        }
    }
    fout<<maxmatches<<"\n";

    for(int i = 1; i <= semigraph1; i++)
    {
        if(left[i])
            fout<<i<<" "<<left[i]<<"\n";
    }


}



int main()
{

    int n,m,e;
    fin>>n>>m>>e;
    int maxi = max(n,m);
    Graph g(maxi,e,1);
    g.matching(n,m);

    return 0;
}