#414. 最短路计数

最短路计数

题目描述

给出一个 N\red N 个顶点 M\red M 条边的无向无权图,顶点编号为 1N\red {1 \sim N}。问从顶点 1\red 1 开始,到其他每个点的最短路有几条。

输入格式

第一行包含 2\red 2 个正整数 N\red N,M\red M,为图的顶点数与边数。

接下来 M\red M行,每行两个正整数 x\red x,y\red y,表示有一条顶点 x\red x 连向顶点 y\red y 的边,请注意可能有自环与重边。

输出格式

输出 N\red N 行,每行一个非负整数,第 i\red i 行输出从顶点 1\red 1 到顶点 i\red i 有多少条不同的最短路,由于答案有可能会很大,你只需要输出 Mod100003\red {Mod100003} 后的结果即可。

如果无法到达顶点 i\red i 则输出 0\red 0

样例

输入样例

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出样例

1
1
1
2
4

提示

使用图论编辑器

1\red 15\red 5 的最短路有 4\red 4 条,分别为 2\red 21245\red {1→2→4→5}2\red 21345\red {1→3→4→5}(由于 45\red {4→5} 的边有 2\red 2 条)。

对于 20%\red {20\%} 的数据,N100\red {N≤100}

对于 60%\red {60\%} 的数据,N1000\red {N≤1000}

对于 100%\red {100\%} 的数据,1N100000,0M200000\red {1≤N≤100000,0≤M≤200000}

image