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.

### 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