405007 - 最短路计数

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

顶点1到顶点5有4条最短路，分别为（1→2→3→5两条，1→2→4→5两条，因为1→2的边有两条）。