问题 AG: 赵子龙七进七出

内存限制:512 MB 时间限制:2.000 S
评测方式:文本比较 命题人:
提交:215 解决:69

题目描述

赵云背着阿斗,被曹军堵截,他现在在山口的位置,而突破在遥远的东方。赵子龙特别着急,想赶紧把阿斗还给刘备让他摔一摔。
我们可以把密密麻麻人群中的空隙看作点,把那些赵云的马可以跳上的盾牌看作边,那么有 $n$ 个点,$m$ 条有向边,问子龙的最少前进步数。
但是子龙的这匹马,它有点点神经质,它是数字3的爱好者,一下子得跳过三条边,而三次算一步。
所以如果有这么一种情况1-->2--->3-->1 如果起点是1终点是2 那么,子龙就会因为它那马而永远陷入曹军的包围中,如果是这种情况就输出-1

$2 \leq n \leq 10^5$ ,$0 \leq m \leq min(10^5,\frac{n(n+1)}{2})$

$1 \leq u_i,v_i \leq n$ and $u_i \neq v_i$

$(u_i,v_i) \neq (u_j,v_j)$  where  $i \neq j $

最后一行输入起点 $S$ 和终点 $T$

$ 1 \leq S,T \leq n$ 

$ S \neq T$ 

输入

n  m
u1 v1
u2 v2
...
un vn
S  T

输出

输出一个整数,代表最少前进步数或者-1

样例输入 复制

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

样例输出 复制

2

提示

点击查看源网页