FOREST  K Edgedisjoint Branchings
Given a directed graph, may contains repeated edges. We assume that the graph contains and only contains K edgedisjoint 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 edgedisjoint 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 edgedisjoint branchings.
Then next (N1)*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 N1 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.
hide comments
Murali:
20101228 19:23:53
I always get wrong answer.

Added by:  Fudan University Problem Setters 
Date:  20071201 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO OBJC SQLITE 
Resource:  g201513 