Given a bipartite graph, the vertices on the left side are numbered $1 \sim L$, and the vertices on the right side are numbered $1 \sim R$.

There are $M$ edges, where the $i$-th edge connects the $a_i$-th vertex on the left to the $b_i$-th vertex on the right.

Find a maximum matching for this bipartite graph.

Input

The first line of input contains three integers $L$, $R$, and $M$.

Each of the next $M$ lines contains two integers $a_i$ and $b_i$, describing an edge. Multiple edges between the same pair of vertices may exist.

Output

The first line of output contains an integer $K$, representing the size of the maximum matching.

Each of the next $K$ lines contains two integers $c_i$ and $d_i$, representing that the $c_i$-th vertex on the left is matched with the $d_i$-th vertex on the right.

If there are multiple valid solutions, you may output any one of them.

Examples

Input 1

3 2 3
1 1
2 2
3 2

Output 1

2
1 1
3 2

Subtasks

For all data, $1 \le L, R \le 2 \cdot 10^5$, $1 \le M \le 6 \cdot 10^5$, $1 \le a_i \le L$, $1 \le b_i \le R$.