Maximum matching

A graph $G=(V,E)$ is called bipartite if its vertex set $V$ can be divided into two subsets $A$ and $B$ such that every edge in $E$ connects a vertex from $A$ to a vertex from $B$.

A matching $P$ is any subset of $E$ such that no two edges in this subset share a common vertex.

A maximum matching is a matching that contains the largest number of edges.

Find a maximum matching in the given bipartite graph.

Input

In the first line, three numbers $n,m$, and $k(1\le n,m\le 100,1\le k\le 10000)$ are given, 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 next $k$ lines contains two integers $u_i$ and $v_i$, indicating that vertex $u_i$ from set $A$ is connected to vertex $v_i$ from set $B$. The vertices in sets $A$ and $B$ are numbered independently, starting from one. All input numbers are integers.

Output

In the first line, print the number $l$ of edges in the maximum matching. Then print $l$ lines, each containing two numbers: $a$ and $b$, where $a$ is a vertex from set $A$, and $b$ is the corresponding vertex from set $B$ in the matching. The printed edges must form a maximum matching.

Examples