Bonds

Problem Description

Given an undirected connected graph with N points and M edges. ?? wants to know the number of occurrence in all bonds of graph for every edge.The index of points starts from 0. An edge cut E of a Graph G is a set of edges of G and the G would be disconnected after deleting all the edges of E. A bond of a graph is an edge cut does not have any other edge cut as a proper subset.

Input

The first line of the input gives the number of test cases T; T test cases follow. Each test case consists of two integers: N, M, followed by M lines, each line contains two integers u, v, implying an undirected edge between u and v. limits T <= 20 2 <= N <= 20 N-1 <= M <= N*(N-1)/2 Edges are distinct. No edge connects to the point itself. N is larger than 10 in no more than 5 cases.

Output

For each test case output “Case #x: y1 y2 … yN” (without quotes), where x is the test case number (starting from 1), and yi is the occurrence times in all bonds of i-th edge.

Sample Input

2
3 3
0 1
0 2
1 2
3 2
0 1
0 2

Sample Output

Case #1: 2 2 2
Case #2: 1 1

Hint

In first case, {(0,1),(0,2)} , {(0,1),(1,2)} , {(0,2),(1,2)} are bonds. In second case, {(0,1)},{(0,2)} is bond.

Author

FZU

Source

2016 Multi-University Training Contest 4