最短路计数

题目描述

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

输入输出格式

输入格式


第一行包含$2$个正整数$N,M$,为图的顶点数与边数。 接下来$M$行,每行$2$个正整数$x,y$,表示有一条顶点$x$连向顶点$y$的边,请注意可能有自环与重边。

输出格式


共$N$行,每行一个非负整数,第$i$行输出从顶点$1$到顶点$i$有多少条不同的最短路,由于答案有可能会很大,你只需要输出$ ans \bmod 100003$后的结果即可。如果无法到达顶点$i$则输出$0$。

输入输出样例

输入样例 #1

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

输出样例 #1

1
1
1
2
4

说明

$1$到$5$的最短路有$4$条,分别为$2$条$1-2-4-5$和$2$条$1-3-4-5$(由于$4-5$的边有$2$条)。 对于$20\%$的数据,$N ≤ 100$; 对于$60\%$的数据,$N ≤ 1000$; 对于$100\%$的数据,$N<=1000000,M<=2000000$。