Code Submission Evaluation System Login

CSES Problem Set

School Dance


Task | Statistics


CSES - School DanceCSES - School Dance

Time limit:1.00 s Memory limit:512 MB

There are $n$ boys and $m$ girls in a school. Next week a school dance will be organized. A dance pair consists of a boy and a girl, and there are $k$ potential pairs.

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
Example

Input:
3 2 4
1 1
1 2
2 1
3 1


Output:
2
1 2
3 1