时间限制： 1.0 秒

空间限制： 256 MB

题目描述

$N$ 个城市，标号从 $0$ 到 $N−1$，$M$ 条道路，第 $K$ 条道路（$K$ 从 $0$ 开始）的长度为 $2^K$，求编号为 $0$ 的城市到其他城市的最短距离。

输入格式

从标准输入读入数据。

第一行两个正整数 $N,M$，表示有 $N~(2 \le N \le 10000)$ 个城市，$M~(1 \le M \le 50000)$ 条道路

接下来 $M$ 行，每行两个整数，表示相连的两个城市的编号。

输出格式

输出到标准输出。

$N−1$ 行，表示 $0$ 号城市到其他城市的最短路，如果无法到达，输出 $−1$，数值太大的以 $\bmod~100000$ 的结果输出。

4 4
1 2
2 3
1 3
0 1

8
9
11

来源

远古时期上海交通大学考研机试题，数据范围有所加强。