Country X

Country X is a country with special structure.

1. It consists of N cities. The indices of the cities are from 0 to N - 1.
2. There are exact M roads between cities. A road is a bidirectional path that connects two different cities. There is at most one road between any two cities. There are no roads connect a city to itself.
3. You can travel from each city to any other cities using these roads. In other words, all the cities are in one connect component.
4. There is exact one special city called centre city X. When X is removed (the roads connect with X are also removed), the cities are partitioned into K parts. There are no roads between any two parts. For each part, you can travel from each city to any other cities in this part (each of the K parts is a connect component).
5. Most important of all, each of the K parts is identical to each other.

Now given N, M, and K, you are asked to construct a valid structure for Country X.

There are no more than 100 cases. For each case, there is only one line giving 3 integers N M K (2 <= N <= 500, 0 <= M <= 10000, 1 <= K <= N).

If there isn't a valid structure, output "Invalid". Otherwise, you need to output all the M roads in M lines. A road is a pair "A B" meaning there is a road between city A and city B (0 <= A, B < N, A != B). If there are more than one valid structure, you should output the lexicographically smallest list of roads. A list of roads R [R1, R2, ... RM] is lexicographically smaller than Q [Q1, Q2, ... QM] if R contains a smaller road at the first index where they differ. A road "A B" is smaller than the road "C D" if A < C or A = C and B < D.

7 6 3
6 6 3

0 1
0 2
0 3
1 4
2 5
3 6
Invalid

hhanger@ZJU

HDOJ 5th Anniversary Contest