1499：最短路计数

题目描述

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

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $x$ 和 $y$，表示顶点 $x$ 和顶点 $y$ 之间有一条无向边。

输出格式

输出 $N$ 行，每行一个非负整数。第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路。由于答案有可能会很大，只需要输出结果对 $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

• 从顶点 $1$ 到顶点 $1$：只有 $1$ 条路径（不动），长度为 $0$，输出 $1$。
• 从顶点 $1$ 到顶点 $2$：只有 $1$ 条最短路 $1→2$（长度为 $1$），输出 $1$。
• 从顶点 $1$ 到顶点 $3$：只有 $1$ 条最短路 $1→3$（长度为 $1$），输出 $1$。
• 从顶点 $1$ 到顶点 $4$：有 $2$ 条最短路（长度均为 $2$）：
  • $1→2→4$
  • $1→3→4$ 输出 $2$。
• 从顶点 $1$ 到顶点 $5$：有 $4$ 条最短路（长度均为 $3$）：
  • $1→2→4→5$（第一条 $4→5$ 的边）
  • $1→2→4→5$（第二条 $4→5$ 的边）
  • $1→3→4→5$（第一条 $4→5$ 的边）
  • $1→3→4→5$（第二条 $4→5$ 的边） 输出 $4$。

注意：图中 $4$ 和 $5$ 之间有两条不同的边（重边），因此最短路数量会受到影响。

数据范围

• 对于 $20\%$ 的数据，$N \le 100$
• 对于 $60\%$ 的数据，$N \le 1000$
• 对于 $100\%$ 的数据，$1 \le N \le 100000$，$0 \le M \le 200000$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB