**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

- 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