F - 被堵塞的道路

得分：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$的最短距离，当除了边$i$以外的所有边都可通过时，如果从顶点$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$行应该包含从顶点$1$到顶点$N$的最短距离，当除了边$i$以外的所有边都可通过时，如果从顶点$1$无法达到顶点$N$，则输出-1。

3 3
1 2
1 3
2 3

1
2
1

4 4
1 2
2 3
2 4
3 4

-1
2
3
2

当除了边$1$以外的所有边都可通过时，从顶点$1$无法到达顶点$N$，因此对应的行应输出-1。

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

1
1
3
1
1
1
1
1
1
1

4 1
1 2

-1