← 返回题目
题库练习 [ABC132E] Hopscotch Addict
← 上一题 下一题 →

A7638 | [ABC132E] Hopscotch Addict

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

Ken 君非常喜欢玩“けんけんぱ”。今天，他决定在一个有向图 $G$ 上玩这个游戏。$G$ 由 $N$ 个编号为 $1$ 到 $N$ 的顶点和 $M$ 条边组成，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

Ken 君一开始站在顶点 $S$，他想通过“けんけんぱ”移动到顶点 $T$。一次“けんけんぱ”操作指的是：连续进行 $3$ 次“从当前所在顶点选择一条出边，移动到该边所连接的顶点”的操作。

请你判断 Ken 君是否能够从顶点 $S$ 移动到顶点 $T$，如果可以，请输出最少需要多少次“けんけんぱ”操作。如果在一次“けんけんぱ”操作的中途经过顶点 $T$，也不算到达顶点 $T$，只有在完成一次完整的“けんけんぱ”操作后停在顶点 $T$，才算到达。

输入格式

输入按以下格式从标准输入读入。

> $N$ $M$
> $u_1$ $v_1$
> $u_2$ $v_2$
> $\vdots$
> $u_M$ $v_M$
> $S$ $T$

输出格式

如果无论进行多少次“けんけんぱ”操作都无法从顶点 $S$ 移动到顶点 $T$，输出 $-1$。如果可以移动到，输出所需的最小“けんけんぱ”操作次数。

输入输出样例

输入 #1
4 4
1 2
2 3
3 4
4 1
1 3
输出 #1
2
输入 #2
3 3
1 2
2 3
3 1
1 2
输出 #2
-1
输入 #3
2 0
1 2
输出 #3
-1
输入 #4
6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6
输出 #4
2
C++ 编辑器
输入
输出