#include <bits/stdc++.h>
using namespace std;
fstream f("cuplaj.in");
ofstream g("cuplaj.out");
const int NMAX=10005,INF=0x3F3F3F3F;
int n,m,e,x,y,c,maxx,no_of_pictures;
bool SCALING=0;///you can choose between having scaling and not having scaling
///it is better without scaling on edges with lower costs, but on high cost edges, scaling helps a lot
struct edge
{
int node,flow,capacity,index;
};
vector<int>level,skip;
vector<edge>graph[2*NMAX];///because we will double the nodes
void add_edge(int x,int y)
{
graph[x].push_back({y,0,1,0});///to node,flow,capacity,index
graph[y].push_back({x,0,0,0});///reverse edge:to node,flow,capacity,index
graph[x].back().index=graph[y].size()-1;///index from adjacency list of y
graph[y].back().index=graph[x].size()-1;///index from adjacency list of x
}
void read_and_create_graph()
{
maxx=c=1;///because we do maximum matching in a bipartite graph
f>>n>>m>>e;
for(int i=1; i<=e; i++)
{
f>>x>>y;
add_edge(x,y+n);///we add an edge from the node on the left to the node on the right
}
for(int i=1; i<=n; i++) ///we add the edges from the source
add_edge(n+m+1,i);
for(int i=1; i<=m; i++) ///we add the edges to the terminal
add_edge(i+n,n+m+2);
}
bool bfs(int s,int t,int limit)
{
level.assign(n+m+3,-1);///because we do maximum matching in a bipartite graph and we have n+m+2 nodes
level[s]=0;
queue<int>q;
q.push(s);
while(!q.empty())
{
int node=q.front();
q.pop();
for(edge& link:graph[node])
if(link.capacity-link.flow>0 && level[link.node]==-1 && (!SCALING || link.capacity-link.flow>=limit))///if I can still push flow and the next node is not visited
{
level[link.node]=level[node]+1;
q.push(link.node);
}
}
return level[t]!=-1;///if t was visited it will return 1,otherwise 0
}
int dfs(int node,int t,int cur_flow)
{
if(node==t)
return cur_flow;
for(; skip[node]<(int)graph[node].size(); skip[node]++)///we start from the pointer we have for this node
{
int next=graph[node][skip[node]].node;
edge& link=graph[node][skip[node]];///for simplicity
if(link.capacity-link.flow>0 && level[node]+1==level[next])///if I can still push flow and the node is not visited and we only go forward
{
int bottleNeck=dfs(next,t,min(cur_flow,link.capacity-link.flow));
if(bottleNeck>0)
{
link.flow+=bottleNeck;///update on the normal edge
graph[next][link.index].flow-=bottleNeck;///update on the reverse edge
return bottleNeck;
}
}
}
return 0;
}
int maxflow(int s,int t)
{
int max_flow=0;
skip.resize(n+m+3);///because we do maximum matching in a bipartite graph and we have n+m+2 nodes
for(int limit=SCALING ? (1<<(int(log2(maxx)))) : 1; limit>0; limit=limit/2)
while(bfs(s,t,limit))
{
fill(skip.begin(),skip.end(),0);///for pruning dead ends
for(int new_flow=dfs(s,t,INF); new_flow!=0; new_flow=dfs(s,t,INF))///as long as we can find a new path we increase the max_flow
max_flow+=new_flow;
}
return max_flow;
}
void write()
{
g<<maxflow(n+m+1,n+m+2)<<'\n';///the maximum flow is equal to the number of matchings in our graph
for(int i=1; i<=n; i++)
for(int j=0; j<graph[i].size()-1; j++) ///because we don't want to take the source into consideration
if(graph[i][j].flow==1)
g<<i<<' '<<graph[i][j].node-n<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
read_and_create_graph();
write();
return 0;
}