Given a directed graph, may contains repeated edges. We assume that the graph contains and only contains K edge-disjoint branchings rooted by node 0.
A branching for a graph is a set of directed edges that from a certain root (root, in this problem, is node 0) we can find one path to every other node in the graph by only the edges in the branching.
K edge-disjoint branching is K branchings that share no common edges.
Your task which is easy and funny is to find out the K branchings.

Input

The first line of input contains a single integer T, (T<=20), denoting the number of test cases.
For each test case:
The first line contains two integers N and K, (2<=N<=500,2<=K<=6), which is the number of the nodes in the graph and the number of edge-disjoint branchings.
Then next (N-1)*K lines contains the information about the edges. There are 2 integers X and Y in every line, meaning there exist an edge from X to Y in the graph.

Output

You should output the branchings you have found.
For every test cases, print the number of test case at the start of output, then you should output K lines.
Each line is about a branching which contains N-1 integers that the ID of the edges in this branching.
The ID of edges starts with 0. Every edge will appear and only appear once in the output.
See samples for further details.

Example

Input:
2
2 2
0 1
0 1
3 2
0 1
0 2
2 1
1 2

Output:
Case 1:
0
1
Case 2:
0 3
1 2

Test data have been enhanced.