Bipartite Graph Matching 2

Problem Description

You are given a bipartite graph with $L$ vertices on the left side and $R$ vertices on the right side, connected by $m$ edges. Find a maximum matching and output one such matching.

Input Format

The first line contains three integers $L, R, m\ (1 \le L, R \le 10^5, 1 \le m \le 2 \times 10^5)$.

Each of the next $m$ lines contains two integers $u, v\ (0 \le u < L, 0 \le v < R)$, indicating an edge. There are no duplicate edges.

Output Format

The first line outputs one number: the size of a maximum matching.

Then output several lines, each containing two numbers, representing an edge in the maximum matching.

Sample Input

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2

Sample Output

3
0 0
1 1
2 2