题目描述

给定一个有向图，有 $N$ 个顶点和 $M$ 条边。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $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$ 行应该包含当除了边 $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$ 之外的所有边都可通过时，从顶点 $1$ 无法到达顶点 $N$，因此对应的行包含 -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