时间限制： 1.0 秒

空间限制： 256 MB

题目描述

在这个古老的王国中，有 $N$ 座城市，编号从 $0$ 到 $N-1$。城市之间通过 $M$ 条双向道路连接。

这些道路的修建历史非常悠久，每条道路都有一个特定的编号，从 $0$ 到 $M-1$。由于某种神秘的魔法力量，第 $k$ 号道路（$0 \le k < M$）的长度恰好是 $2^k$。

现在你需要计算从王国首都（编号为 $0$ 的城市）出发，到达其他所有城市（编号 $1$ 到 $N-1$）的最短路径长度。

由于路径长度可能非常大，请输出长度对 $100000$ 取模后的结果。如果某个城市无法到达，请输出 $-1$。

输入格式

从标准输入读入数据。

第一行包含两个整数 $N$ 和 $M$，分别表示城市的数量和道路的数量。

接下来 $M$ 行，第 $i$ 行（$1 \le i \le M$）包含两个整数 $u, v$，表示第 $i-1$ 号道路（长度为 $2^{i-1}$）连接了城市 $u$ 和城市 $v$。

输出格式

输出到标准输出。

输出共 $N-1$ 行。 第 $i$ 行输出从城市 $0$ 到城市 $i$ 的最短路径长度对 $100000$ 取模后的结果。如果无法到达，输出 $-1$。

4 4
0 1
1 2
0 2
2 3

1
3
11

样例 1 解释

共有 4 个城市，4 条道路：

• 0号路：连接 (0, 1)，长度 $2^0 = 1$
• 1号路：连接 (1, 2)，长度 $2^1 = 2$
• 2号路：连接 (0, 2)，长度 $2^2 = 4$
• 3号路：连接 (2, 3)，长度 $2^3 = 8$

计算最短路：

• 到城市 1：走 0号路 (0->1)，距离为 1。
• 到城市 2：
  • 路径 A：0->2 (走2号路)，距离 4。
  • 路径 B：0->1->2 (走0号路和1号路)，距离 $1+2=3$。
  • 因为 $3 < 4$，所以最短距离为 3。
• 到城市 3：最优路径为 0->1->2->3，距离 $1+2+8=11$。

样例 2

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

1
3
7
15

样例 2 解释

这是一条 0-1-2-3-4 的链，以及一条直接连接 0-4 的边（这是第4条输入，对应4号路，长度 $2^4=16$）。 虽然 0-4 直连看起来只有一条边，但长度是 16。 而走链 0-1-2-3-4 的总长度是 $1+2+4+8 = 15$。 因为 $15 < 16$，所以到城市 4 的最短路是 15。

子任务

对于所有测试数据，保证 $2 \le N \le 2000$，$1 \le M \le 2000$，图一定连通。