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

• 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