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.
Sample Input
1
1 1000000 0
Sample Output
