Problem Description
Country X is a country with special structure.
- It consists of N cities. The indices of the cities are from 0 to N - 1.
- 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.
- You can travel from each city to any other cities using these roads. In other words, all the cities are in one connect component.
- 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).
- 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.
Input
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).
Output
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.
Sample Input
7 6 3
6 6 3
Sample Output
0 1
0 2
0 3
1 4
2 5
3 6
Invalid
