最短路计数

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图。

问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第 $1$ 行包含两个正整数 $N$，$M$。

接下来 $M$ 行，每行两个正整数 $x, y$ 表示存在一条由顶点 $x$ 到顶点 $y$ 的边。（可能存在重边和自环）

输出格式

输出 $N$ 行，每行一个非负整数。

第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 的不同最短路个数。

由于数据可能很大，你只需要输出 $ans \bmod 100003$ 的结果。

若顶点 $1$ 不能到达顶点 $i$，请输出 $0$。

样例输入

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

样例输出

1
1
1
2
4

数据范围

$1 \le N \le 10^6$，$1 \le M \le 2 \times 10^6$。

提示

由于数据量较大，请使用较为快速的输入/输出方式。