Problem G. Generations

Author:G. Grenkin, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Two fathers and two sons walked together... It is well known that this could describe a group of either 3 or 4 people.

Now let's say that A fathers and B sons walked together. Could it be that this group consisted of exactly N different persons?

A person is counted as a father if there is his son among the group. A person is counted as a son if there is his father among the group. Each father can have one or more sons, each son must have exactly one father. Father of a person can not be this person's descendant. Each person must me either a son, a father, or both.

Your program must, given numbers A B N, output corresponding father-son relationship or determine that it does not exist.

Input file format

Input file contains integers A B N.

Output file format

Output file must contain a number of father-son relationships M followed by M pairs ai bi where ai is a number of the father, bi is a number of the son (1 ≤ ai, bi ≤ N).

All pairs must be different. If there are several solutions, output any of them. If it is impossible for a group to consist of N persons, output file must contain a single integer 0.

Constraints

1 ≤ A ≤ B ≤ 100

1 ≤ N ≤ 200

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2 3
2
3 1
1 2
2
2 2 4
2
1 2
3 4
3
2 2 5
0

0.074s 0.010s 13