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) ≤ C * nk holds for any positive n.

Help him to do it.

Input

The first line contains four integers n, m, s, t (1 ≤ n, m ≤ 105). The vertices are numbered from 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 that satisfies the problem statement. If there are no such numbers, output "-1".