Description

给定一个n个点m个边的有向图，所有边长度为1，现问对于每条边，设这条边从节点x出发指向节点y，将这条边从图中删除之后，x到y的最短路为多少

Input

首先输入一个整数Q(0 < Q ≤ 10)，表示有Q组样例

每组样例首先输入两个整数n, m (0 < n ≤ 500, 0 < m ≤ 10000)，表示该组样例所表示的图中有n个点和m条有向边，之后m行，每行两个个整数x, y, (1 ≤ x, y ≤ n)，表示有一条编号为x的节点出发指向编号为y的节点的边,输入保证对于任意对整数对(x, y)，最多存在一条从x指向y的边，但可能同时存在从x指向y的边和y指向x的边

Output

对于每组样例，首先输出样例编号，之后输出m个数，以此表示删除这条边后，这条边原来连接的两个节点之间的最短路，如果删除这条边之后两个点之间不存在路径相连，输出0，具体格式见sample output

Sample Input

3

3 3

1 2

2 3

1 3

3 3

1 2

2 1

1 3

3 6

1 2

2 1

1 3

3 1

3 2

2 3

Sample Output

Case 1: 0 0 2

Case 2: 0 0 0

Case 3: 2 2 2 2 2 2

此题广搜竟然可以AC。。