Petr wants to use his own algorithm to solve a very important problem for a directed graph G with n vertices and m arcs. Unfortunately, Petr cannot calculate a complexity of his algorithm. He only knows that the complexity depends on the order of growth of value F(N) which denotes the number of walks of length N from vertex s to vertex t in G. Petr wants to bound F(N) with a polynomial of minimal degree, that is, to find the minimal non-negative integer k such that for some fixed number C inequality F(N) ≤ CNk holds for any positive N. Help him to do it.
Input
The first line contains 4 space-separated integers n, m, s, t (1 ≤ n, m ≤ 100000). The vertices are numbered 1 to n. Each of the next m lines contains two space-separated integers—numbers of starting and ending vertices of the current arc. The graph doesn't contain multiple arcs but may contain loops.
Output
Output the minimal integer k which satisfies the problem statement.
If there are no such numbers, output “−1”.
Samples
input | output |
---|
2 3 1 2
1 1
1 2
2 2
| 1 |
3 6 1 2
1 2
2 1
1 3
3 1
2 3
3 2
| -1 |
Problem Author: Ivan Burmistrov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009