Maximum matching

Input

The first line contains three integers $n$, $m$, and $k$ (1 \le n, m \le 100,\ 1 \le k \le 10000), where $n$ is the number of vertices in set $A$, $m$ is the number of vertices in set $B$, and $k$ is the number of edges in the graph.

Each of the following $k$ lines contains two integers u_i and v_i, denoting that vertex u_i from set $A$ is connected with vertex v_i from set $B$. Vertices in sets $A$ and $B$ are numbered independently, starting from one.

All input numbers are integers.

Output

In the first line, output the number $l$ — the number of edges in the maximum matching.

Then output $l$ lines, each containing two integers $a$ and $b$: a vertex $a$ from set $A$ and the corresponding vertex $b$ from set $B$ in the matching.

The printed edges must form a maximum matching.

Examples