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) ≤ CN^k holds for any positive N. Help him to do it.

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 the minimal integer k which satisfies the problem statement. If there are no such numbers, output “−1”.