
ZOJ Problem Set  3438
Many of you know bipartite graph, which is an undirected graph whose vertices can be divided into two nonempty 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 nonempty 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. InputThe 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 V_{1} V_{2} (1 <= V_{1} V_{2} <= V), means there should be an edge between V_{1} and V_{2}. OutputFor 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. Sample Input1 1 1000000 0 Sample OutputAuthor: HANG, Hang Contest: Let's Celebrate the 100th Contest on ZOJ! 