问题 3269 --传送（transfer）

3269: 传送（transfer）

时间限制: 1 Sec  内存限制: 256 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

  存在 n 个小镇，m 条传送通道，第 i 条双向连结 ui , vi 两个小镇，经过每个传送通 道需要花费 1 分钟。特别地，可能存在 ui = 0，表示该条传送通道只规定了一端，另一 端待定。存在 n 个独立询问，对于 i = 1, 2, , n ，钦定所有未确定的 ui 均为 i ，求从小 镇 1 到小镇 n 最小耗费的时间。若无法到达输出 −1 。 

输入

第一行输入两个整数 n, m 。 接下来 m 行，每行输入两个整数 ui , vi 。

输出

输出一行 n 个整数，表示每个询问的答案。

样例输入

样例1
3 2
0 2
1 2
样例2
5 5
1 2
1 3
3 4
4 5
0 2

样例输出

样例1
-1 -1 2
样例2
3 3 3 3 2

提示


【数据范围】 



数据约束和子任务



 2 ≤ N ≤ 3 × 10^5 



1 ≤ M ≤ 3 × 10^5 



0≤ Ui < Vi ≤ N 



没有重边 

来源

普及组模拟测试第一套第5题 

[提交][状态]