1154 . Graph Construction

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

NTU PK NTU PK 2010

Description

Given three integers N, M, K, please construct a simple graph G with the following conditions:


  1. G has N vertices and M edges, the vertices are labeled from 0 to N-1.

  2. G is connected.

  3. There exists a centre vertex v. If v is removed from G, G splits into K connected components.

  4. Each of the K connected components is identical to each other.

Input Format

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

Output Format

If there isn't a valid structure, output "Invalid". Otherwise, you need to output all the M edges in M lines. An edge is a pair "A B" meaning an edge between vertex A and vertex B. If there are more than one solution, output the lexicographically smallest one.

Print a blank line after each testcase.

Sample Input 1

7 6 3
6 6 3
4 3 3

Sample Output 1

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

Invalid

0 1
0 2
0 3

Hints

Problem Source

Migrated from old NTUJ.

Bee

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 200
Submit
Back to Top