题目描述

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

输入格式

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

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

输出格式

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

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

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$。