Problem Background

NOIP2014 Senior Group D2T2

Problem Description

In a directed graph $G$, each edge has a length of $1$. You are given a starting point and an ending point, and you need to find a path from the starting point to the ending point in the graph that satisfies the following conditions:

1. All points on the path must have outgoing edges that point to nodes that are directly or indirectly connected to the ending point.
2. Under the condition of satisfying the first condition, the path should be the shortest.

Note: The graph $G$ may contain duplicate edges and self-loops, and the problem guarantees that the ending point has no outgoing edges.

Please output the length of the path that meets the conditions.

Input Format

The first line contains two integers $n$ and $m$ separated by a space, indicating that the graph has $n$ points and $m$ edges.

The next $m$ lines each contain two integers $x$ and $y$ separated by a space, indicating that there is an edge from point $x$ to point $y$.

The last line contains two integers $s$ and $t$ separated by a space, indicating that the starting point is $s$ and the ending point is $t$.

Output Format

The output should be a single line containing an integer, which represents the length of the shortest path that satisfies the problem description. If such a path does not exist, output $-1$.

Sample Input and Output

Sample Input #1

3 2
1 2
2 1
1 3

Sample Output #1

-1

Sample Input #2

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

Sample Output #2

3

Notes

Sample 1 Explanation

As shown in the figure, arrows represent directed roads, and circles represent cities. The starting point $1$ and the ending point $3$ are not connected, so there is no path that satisfies the problem description, hence the output is $-1$.

Sample 2 Explanation

As shown in the figure, the path that satisfies the conditions is $1\to 3\to 4\to 5$. Note that point $2$ cannot be in the answer path because point $2$ is connected to point $6$, which is not connected to the ending point $5$.

Data Range and Constraints

• For $30\%$ of the data, $0<n\le10$, $0<m\le 20$.
• For $60\%$ of the data, $0<n\le100$, $0<m\le 2000$.
• For $100\%$ of the data, $0<n\le 10^4$, $0<m\le 2\times 10^5$, $0<x,y,s,t\le n, x,s\ne t$.

见题面 Input 部分

见题面 Output 部分