分数: 500 点
问题陈述
给你一个有向图 N 顶点和 M 边缘。顶点已编号 1 通过 N,并且边缘已编号 1 通过 M。边缘 i (1 \leq i \leq M) 来自顶点 s_i 到顶点 t_i 的长度为 1.
对于每个 i (1 \leq i \leq M),找到距顶点的最短距离 1 到顶点 N 当除 Edge 之外的所有边 i 还可以,或者打印 -1 如果顶点
从 Vertex 无法访问 N 从 Vertex 无法访问 1.
约束
- 2 \leq N \leq 400
- 1 \leq M \leq N(N-1)
- 1 \leq s_i,t_i \leq N
- s_i \neq t_i
- (s_i,t_i) \neq (s_j,t_j) (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M s_1 t_1 s_2 t_2 \vdots s_M t_M
输出
打印 M 行。
的 i-th 行应包含距顶点的最短距离 1 到顶点 N 当除 Edge 之外的所有边 i 还可以,或者 -1 如果顶点
从 Vertex 无法访问 N 从 Vertex 无法访问 1.
示例输入 1
3 3 1 2 1 3 2 3
示例输出 1
1 2 1
示例输入 2
4 4 1 2 2 3 2 4 3 4
示例输出 2
-1 2 3 2
顶点 N 从 Vertex 无法访问 1 当除 Edge 之外的所有边 1 还可以,所以对应的行包含 -1.
示例输入 3
5 10 1 2 1 4 1 5 2 1 2 3 3 1 3 2 3 5 4 2 4 3
示例输出 3
1 1 3 1 1 1 1 1 1 1
示例输入 4
4 1 1 2
示例输出 4
-1