阻断的道路

题目描述

给你一个有 $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$ 的最短距离；如果顶点 $N$ 无法从顶点 $1$ 到达，则输出 -1。

输入格式

输入按以下格式从标准输入给出。

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

输出格式

输出 $M$ 行。

第 $i$ 行应输出当除边 $i$ 以外的所有边都可以通行时，从顶点 $1$ 到顶点 $N$ 的最短距离；如果顶点 $N$ 无法从顶点 $1$ 到达，则输出 -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$ 以外的所有边都可以通行时，顶点 $N$ 无法从顶点 $1$ 到达，因此对应行输出 -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

数据范围

• $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$）
• 输入中的值全部为整数