**Time limit:**1.00 s**Memory limit:**512 MB

Your task is to find out the maximum number of dance pairs and show how this number can be achieved.

**Input**

The first input line has three integers $n$, $m$ and $k$: the number of boys, girls, and potential pairs. The boys are numbered $1,2,\dots,n$, and the girls are numbered $1,2,\dots,m$.

After this, there are $k$ lines describing the potential pairs. Each line has two integers $a$ and $b$: boy $a$ and girl $b$ are willing to dance together.

**Output**

First print one integer $r$: the maximum number of dance pairs. After this, print $r$ lines describing the pairs. You can print any valid solution.

**Constraints**

- $1 \le n,m \le 500$

- $1 \le k \le 1000$

- $1 \le a \le n$

- $1 \le b \le m$

**Example**

Input:

`3 2 4`

1 1

1 2

2 1

3 1

Output:

`2`

1 2

3 1