最短路计数

Grade 100 Open Time Wednesday, 17 June 2020, 6:20 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 6:20 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 6:20 PM
Input file SortPath.in Output file SortPath.out

【题目描述】最短路计数(SortPath)

一个N个顶点M条边的无向无权图(可能有自环与重边),顶点编号为1~N。试求顶点1到其他每个顶点的最短路有几条。

【输入格式】

第一行2个正整数N和M(N≤1 000 000,M≤2 000 000),表示图的顶点数与边数。

随后M行,每行2个正整数x和y,表示顶点x与顶点y有一条边。

【输出格式】

输出N行,每行一个非负整数,依次从小到大输出从顶点1到其他各顶点有多少条不同的最短路(值取100 003的模),如果无路则输出0。

【输入样例】

5 6

1 2

1 2

2 3

2 4

3 5

4 5

【输出样例】

1

2

2

2

4

【样例说明】

顶点1到顶点5有4条最短路,分别为(1→2→3→5两条,1→2→4→5两条,因为1→2的边有两条)。