题目描述

Petr 想用自己的算法解决一个关于有向图 G 的重要问题。

图中有 n 个顶点和 m 条有向边。Petr 不知道自己的算法复杂度是多少，只知道复杂度取决于函数 F(N) 的增长阶。

F(N) 表示：

在图 G 中，从顶点 s 出发，到达顶点 t，长度恰好为 N 的游走（walk）数量。

注意，游走允许重复经过顶点和边。

Petr 希望用次数尽可能低的多项式来限制 F(N)。

也就是说，你需要找到最小的非负整数 k，使得存在某个固定常数 C，满足对于所有正整数 N：

如果不存在这样的 k，说明 F(N) 的增长速度超过任何多项式。

请你求出这个最小的 k。

输入格式

第一行包含四个整数：

n m s t

其中：

顶点编号为 1..n。

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

图中：

• 不存在重边；
• 允许自环。

输出格式

输出满足题意的最小非负整数 k。

如果不存在任何多项式能够作为 F(N) 的上界，则输出：

-1

样例 1

输入

2 3 1 2
1 1
1 2
2 2

输出

1

样例 2

输入

3 6 1 2
1 2
2 1
1 3
3 1
2 3
3 2

输出

-1