风塔跃迁

题目描述

边境上建有 $n$ 座风塔，编号为 $1$ 到 $n$。塔与塔之间存在若干条单向跃迁气流，如果风塔 $u$ 有一股气流可以直接把旅人送到风塔 $v$，就记作一条记录。

旅人阿泽会从风塔 $s$ 出发，每次只能沿着一条气流完成一次跃迁。

阿泽想用尽量少的跃迁次数到达风塔 $t$。请你求出这个最少跃迁次数。如果无法到达，请输出 $-1$。

输入格式

第一行包含四个整数 $n, m, s, t$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示存在一条从风塔 $u$ 到风塔 $v$ 的单向跃迁气流。

输出格式

输出一个整数，表示最少跃迁次数；如果无法到达，输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

4 2 1 4
1 2
2 3

输出 #2

-1

数据范围

对于 $50\%$ 的数据，$1 \le n \le 1000$，$0 \le m \le 5000$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$，$1 \le s, t, u, v \le n$。

建议

一刷、二刷、三刷