题目描述

一张城市通信网共有 $n$ 个节点，编号为 $1 \sim n$，节点之间有 $m$ 条双向连线。

总部位于节点 $1$。现在总部要向所有节点发送一条消息。消息每经过一条连线，就需要恰好 $1$ 单位时间。

对于每个节点 $i$，你需要回答：

从节点 $1$ 出发，恰好按照最短时间把消息送到节点 $i$，一共有多少种不同的路线？

如果两条路线经过的边序列不同，就认为它们是不同的路线。

由于答案可能很大，请对 $100003$ 取模。

如果某个节点无法从节点 $1$ 到达，则它的答案为 $0$。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间有一条双向连线。

数据范围：

• $1 \le n \le 5 \times 10^4$
• $0 \le m \le 1.2 \times 10^5$
• 测试数据不包含重边和自环

输出格式

输出 $n$ 行，第 $i$ 行输出从节点 $1$ 到节点 $i$ 的最短路线条数对 $100003$ 取模后的结果。

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

1
1
1
2
2