# Maximum matching

# Maximum matching

Graph (**V**, **E**) is called bipartite, if its set of vertices **V** can be divided to two subsets **A** and **B** so that any edge from **E** connects vertex from **A** with vertex from **B**.

The matching **P** is any subset **E** such that no its two edges have common vertex.

Maximum matching is a matching where the number of edges is maximal.

Find the maximal matching in a given bipartite graph.

#### Input

The first line contains three numbers **n**, **m** и **k** (**1** ≤ **n**, **m** ≤ **100**, **1** ≤ **k** ≤ **10000**), where **n** is a number of vertices in a set **A**, **m** is a number of vertices in a set **B**, and **k** is a number of edges in a graph. Each of the next **k** lines contains two numbers `u`

and _{i}`v`

, meaning that a vertex _{i}`u`

from set _{i}**A** is connected with an edge with `v`

from set _{i}**B**. The vertices in sets **A** and **B** are numbered separately, starting from one. All given numbers are integers.

#### Output

Print in the first line the number of edges **l** in maximal matching. Then print **l** rows, two numbers in each. The numbers `a`

and _{j}`b`

in the _{j}**j**-th row mean that matching includes the edge between vertex `a`

of the set _{j}**A** and a vertex `b`

of the set _{j}**B**. Printed edges must form a maximum matching.

2 3 4 1 1 1 2 2 2 2 3

2 1 1 2 3