Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3438
Tripartite Graph

Time Limit: 5 Seconds      Memory Limit: 65536 KB      Special Judge

Many of you know bipartite graph, which is an undirected graph whose vertices can be divided into two non-empty disjoint sets U and V such that every edge connnects a vertex in U to one in V, that is, there is no edge that connects a vertex v to another vertex which is in the same set of v. Similarly, a tripartite graph (which is also called Kengdie graph) is an undirected graph whose vertices can be divided into three non-empty disjoint sets U, V and W such that there is no edge that connects a vertex v to another vertex which is in the same set of v. A simple graph is a graph that has no loops and no more than one edge between any two different vertices. A graph is a simple tripartite graph if it is simple and it is a tripartite graph.

You are given two integers V and E, and are asked to construct a simple tripartite graph which has exactly V vertices and E edges. In these E edges, M of them are given to you. Besides, any two of the three disjoint vertices sets must have different sizes.

#### Input

The first line is the number of cases T (T <= 100). For each case, the first line gives three integers V, E and M (1 <= V <= 50, 1,000 <= E <= 1,000,000, 0 <= M <= min(E, 10,000)). Then M lines follow, each gives an edge V1 V2 (1 <= V1 V2 <= V), means there should be an edge between V1 and V2.

#### Output

For each case, output E lines, that are the edges of the graph you construct. If there are multiple solutions, output any one. If there is no such graph, do not output anything.

```1
1 1000000 0
```

#### Sample Output

Author: HANG, Hang
Contest: Let's Celebrate the 100th Contest on ZOJ!
Submit    Status