数据结构基础

【题目描述】最短路计数（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的边有两条）。