【fjwc2014】最短路

2014年2月14日1,2420

Description

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

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。。