题目描述

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

输入格式

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

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

输出格式

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

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

样例

输入样例

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

输出样例

1
1
1
2
4

提示

使用图论编辑器

$\red 1$ 到 $\red 5$ 的最短路有 $\red 4$ 条，分别为 $\red 2$ 条 $\red {1→2→4→5}$ 和 $\red 2$ 条 $\red {1→3→4→5}$（由于 $\red {4→5}$ 的边有 $\red 2$ 条）。

对于 $\red {20\%}$ 的数据，$\red {N≤100}$；

对于 $\red {60\%}$ 的数据，$\red {N≤1000}$；

对于 $\red {100\%}$ 的数据，$\red {1≤N≤100000,0≤M≤200000}$。