Ken loves ken-ken-pa (Japanese version of hopscotch). Today, he will play it on a directed graph G. G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.

First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken-ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Constraints

* 2 \leq N \leq 10^5
* 0 \leq M \leq \min(10^5, N (N-1))
* 1 \leq u_i, v_i \leq N(1 \leq i \leq M)
* u_i \neq v_i (1 \leq i \leq M)
* If i \neq j, (u_i, v_i) \neq (u_j, v_j).
* 1 \leq S, T \leq N
* S \neq T

Input

Input is given from Standard Input in the following format:


N M
u_1 v_1
:
u_M v_M
S T


Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1. If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Examples

Input

4 4
1 2
2 3
3 4
4 1
1 3


Output

2


Input

3 3
1 2
2 3
3 1
1 2


Output

-1


Input

2 0
1 2


Output

-1


Input

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6


Output

2
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            graph.get(sc.nextInt() - 1).add(sc.nextInt() - 1);
        }
        int start = sc.nextInt() - 1;
        int end = sc.nextInt() - 1;
        PriorityQueue<Path> queue = new PriorityQueue<>();
        queue.add(new Path(start, 0, 0));
        int[][] points = new int[3][n];
        for (int i = 0; i < 3; i++) {
            Arrays.fill(points[i], Integer.MAX_VALUE);
        }
        while (queue.size() > 0) {
            Path p = queue.poll();
            if (points[p.count][p.idx] <= p.value) {
                continue;
            }
            points[p.count][p.idx] = p.value;
            for (int x : graph.get(p.idx)) {
                queue.add(new Path(x, p.value + 1, (p.count + 1) % 3));
            }
        }
        if (points[0][end] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(points[0][end] / 3);
        }
    }
    
    static class Path implements Comparable<Path> {
        int idx;
        int value;
        int count;
        
        public Path(int idx, int value, int count) {
            this.idx = idx;
            this.value = value;
            this.count = count;
        }
        
        public int compareTo(Path another) {
            return value - another.value;
        }
    }
   
   
}