题目背景

2025/10/15：加入了一组 hack 数据。

题目描述

给定一简单有向无权图 $G=(V,E)$，对于每条边 $e$，计算 $G\setminus\{e\}$ 中 $1$ 到 $n$ 的最短路。

输入格式

第一行两个正整数 $|V|,|E|$。

之后 $|E|$ 行，每行两个正整数 $u,v$，表示一条 $u$ 到 $v$ 的有向边。

输出格式

对于每条边 $e$，按照输入顺序输出 $G\setminus\{e\}$ 中 $1$ 到 $n$ 的最短路。若删去该边后 $1$ 不能到达 $n$，则输出 $-1$。

7 7
1 2
2 3
3 4
4 7
2 5
5 6
6 4

-1
5
5
-1
4
4
4

23 25
1 2
1 6
2 3
3 4
3 23
4 2
4 15
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 4
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 5
5 23

13
3
20
3
13
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3

提示

样例解释 $\#2$：请注意无向图上的经典做法在有向图上是错误的。

对于所有数据，$1\leq n\leq m\leq10^5$。

如果你会了带权做法（P3238），请去申请图灵奖。