← 返回题目列表

AtCoder · abc218_f

I. 道路受阻

中文机器翻译题面 查看原题

分数: 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