该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

一次逆行

题目描述

给定一张有 $n$ 个点、$m$ 条边的有向图，点的编号为 $1$ 到 $n$。

你需要从点 $s$ 出发，到达点 $t$。

正常情况下，你只能沿着有向边的方向移动。也就是说，如果存在一条边 $u \to v$，那么你可以从 $u$ 走到 $v$。

但是在整个过程中，你可以最多一次逆向经过某条边。

也就是说，如果存在一条边 $u \to v$，你可以选择一次从 $v$ 走到 $u$。

你也可以不使用这次逆行机会。

每经过一条边，无论是正向还是逆向，代价都为 $1$。

请你求出从 $s$ 到 $t$ 的最小代价。

特别地，如果 $s=t$，答案为 $0$。

如果无法到达，输出 -1。

输入格式

第一行输入四个整数 $n,m,s,t$，分别表示点数、边数、起点和终点。

接下来 $m$ 行，每行输入两个整数 $u,v$，表示存在一条从 $u$ 到 $v$ 的有向边。

数据范围：

对于所有测试数据，满足：

保证不存在重复的有向边。

注意，可能同时存在 $u \to v$ 和 $v \to u$。

输出格式

输出一个整数，表示从 $s$ 到 $t$ 的最小代价。

如果无法到达，输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

4 3 1 4
2 1
3 2
3 4

输出 #2

-1

说明/提示

存在边 $3 \to 2$。

正常情况下不能从 $2$ 走到 $3$，但可以使用一次逆行，从 $2$ 逆向经过这条边到达 $3$。

因此可以走：

1 -> 2 -> 3 -> 4 -> 5

总代价为 $4$。