Robot Control

题意翻译

**Description** 有一个 N 个点, M 条边的有向图, 初始有一个机器人在 s 号点. 每个时刻, 这个机器人会随机选择一条从该点出发地边并通过.当机器人到达点 t 时, 它就会自动关闭. 然而这个机器人如果在某个时刻到达自己曾经到过的点的话,它就会爆炸. 因此, 你决定对机器人实施一些命令, 让它在某些时候按照规定的边走, 而非随机选择. 问对机器人最少使用多少条命令可以让它安全到达点 t. **Constraints** N, M ≤ 1e6

题目描述

The boss of the Company of Robot is a cruel man. His motto is "Move forward Or Die!". And that is exactly what his company's product do. Look at the behavior of the company's robot when it is walking in the directed graph. This behavior has been called "Three Laws of Robotics": - Law 1. The Robot will destroy itself when it visits a vertex of the graph which it has already visited. - Law 2. The Robot will destroy itself when it has no way to go (that is when it reaches a vertex whose out-degree is zero). - Law 3. The Robot will move randomly when it has multiple ways to move (that is when it reach a vertex whose out-degree is more than one). Of course, the robot can move only along the directed edges of the graph. Can you imagine a robot behaving like that? That's why they are sold at a very low price, just for those who are short of money, including mzry1992, of course. mzry1992 has such a robot, and she wants to move it from vertex $ s $ to vertex $ t $ in a directed graph safely without self-destruction. Luckily, she can send her robot special orders at each vertex. A special order shows the robot which way to move, if it has multiple ways to move (to prevent random moving of the robot according to Law 3). When the robot reaches vertex $ t $ , mzry1992 takes it off the graph immediately. So you can see that, as long as there exists a path from $ s $ to $ t $ , she can always find a way to reach the goal (whatever the vertex $ t $ has the outdegree of zero or not).  Sample 2 However, sending orders is expensive, so your task is to find the minimum number of orders mzry1992 needs to send in the worst case. Please note that mzry1992 can give orders to the robot while it is walking on the graph. Look at the first sample to clarify that part of the problem.

输入输出格式

输入格式

The first line contains two integers $ n $ ( $ 1<=n<=10^{6} $ ) — the number of vertices of the graph, and $ m $ ( $ 1<=m<=10^{6} $ ) — the number of edges. Then $ m $ lines follow, each with two integers $ u_{i} $ and $ v_{i} $ ( $ 1<=u_{i},v_{i}<=n $ ; $ v_{i}≠u_{i} $ ), these integers denote that there is a directed edge from vertex $ u_{i} $ to vertex $ v_{i} $ . The last line contains two integers $ s $ and $ t $ ( $ 1<=s,t<=n $ ). It is guaranteed that there are no multiple edges and self-loops.

输出格式

If there is a way to reach a goal, print the required minimum number of orders in the worst case. Otherwise, print -1.

输入输出样例

输入样例 #1

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

输出样例 #1

1

输入样例 #2

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

输出样例 #2

1

说明

Consider the first test sample. Initially the robot is on vertex 1. So, on the first step the robot can go to vertex 2 or 3. No matter what vertex the robot chooses, mzry1992 must give an order to the robot. This order is to go to vertex 4. If mzry1992 doesn't give an order to the robot at vertex 2 or 3, the robot can choose the "bad" outgoing edge (return to vertex 1) according Law 3. So, the answer is one.