102185: [AtCoder]ABC218 F - Blocked Roads

Problem Statement

You are given a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the edges are numbered $1$ through $M$. Edge $i$ $(1 \leq i \leq M)$ goes from Vertex $s_i$ to Vertex $t_i$ and has a length of $1$.

For each $i$ $(1 \leq i \leq M)$, find the shortest distance from Vertex $1$ to Vertex $N$ when all edges except Edge $i$ are passable, or print -1 if Vertex $N$ is unreachable from Vertex $1$.

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$s_1$ $t_1$
$s_2$ $t_2$
$\vdots$
$s_M$ $t_M$

Output

Print $M$ lines.

The $i$-th line should contain the shortest distance from Vertex $1$ to Vertex $N$ when all edges except Edge $i$ are passable, or -1 if Vertex $N$ is unreachable from Vertex $1$.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

1
2
1

Sample Input 2

4 4
1 2
2 3
2 4
3 4

Sample Output 2

-1
2
3
2

Vertex $N$ is unreachable from Vertex $1$ when all edges except Edge $1$ are passable, so the corresponding line contains -1.

Sample Input 3

5 10
1 2
1 4
1 5
2 1
2 3
3 1
3 2
3 5
4 2
4 3

Sample Output 3

1
1
3
1
1
1
1
1
1
1

Sample Input 4

4 1
1 2

Sample Output 4

-1

问题描述

给你一个有向图，包含 $N$ 个顶点和 $M$ 条边。顶点编号为 1 到 $N$，边编号为 1 到 $M$。第 $i$ 条边（$1 \leq i \leq M$）从顶点 $s_i$ 指向顶点 $t_i$，长度为 1。

对于每一条边 $i$ $(1 \leq i \leq M)$，当除了第 $i$ 条边之外的所有边都是可通行的，求从顶点 1 到顶点 $N$ 的最短距离。如果从顶点 1 无法到达顶点 $N$，则输出 -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$ 行应包含当除了第 $i$ 条边之外的所有边都是可通行的时，从顶点 1 到顶点 $N$ 的最短距离，如果从顶点 1 无法到达顶点 $N$，则输出 -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

当除了第 $1$ 条边之外的所有边都是可通行的时，顶点 $N$ 无法从顶点 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