题目描述

给定一张 $n$ 个点，$m$ 条边的有向图，每条边的边权均为 $1$。请对于每一个 $i\in [1,m]$ 求出从点 $1$ 到 $n$ 的不经过第 $i$ 条边的最短路长度。

输入格式

第一行为 $N,M(1\le N\le 400)$。

接下来 $M$ 行，每行为一条由 $x$ 连向 $y$ 的有向边。

保证没有重边和自环。

输出格式

输出总共 $M$ 行，第 $i$ 行为删除掉输入的第 $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

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