配点 : 1000 点
問題文
N 頂点 M 给出了边的无向图。在每个顶点 它们的编号最大为 1 我决定将所有值添加到 N 。i 第一条边是顶点 A_i 和顶点 B_i 是平局。
1 以上 N 以下所有整数 请回答以下有关 k 的问题。
頂点 1 到顶点 当考虑通过跟踪多个边缘移动到 k 时,输出要跟踪的最小边缘数。但是,如果无法移动 -1 。
制約
- 所有输入均为整数
- 1 \le N \le 10^5
- 0 \le M \le \min(10^5,\frac{N(N-1)}{2})
- 1 \le A_i < B_i \le N
- 图中没有重边或自环。
入力
输入将以以下形式从标准输入给出。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
总体 请输出 N 行。 请打印
i 行中, k=i 的答案。
入力例 1
3 2 1 3 2 3
出力例 1
0 2 1
- 頂点 1 到顶点 当考虑通过跟踪多个边缘移动到 1 有 0 假设可以沿着书本的边缘移动。 当导航至
- 頂点 1 到顶点 当考虑通过跟踪多个边缘移动到 2 时, 使用 1 \rightarrow 3 \rightarrow 2 移动可最大限度地减少要跟踪的边数。
- 頂点 1 到顶点 当考虑通过跟踪多个边缘移动到 3 时, 使用 1 \rightarrow 3 移动可最大限度地减少要跟踪的边数。
入力例 2
6 6 1 4 2 3 3 4 5 6 1 2 2 4
出力例 2
0 1 2 1 -1 -1
给定的图不一定是连通的。