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.
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.
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.
3 2 4 1 1 1 2 2 1 3 1· · \n · \n · \n · \n · \n
2 1 2 3 1\n · \n · \n