Home STD Contest Notification Clarification Problems Ranklist Status Print Sign Out
SolutionMore...

Key Vertex

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 65    Accepted Submission(s): 1


Problem Description
You need walking from vertex S to vertex T in a graph. If you remove one vertex which stops you from walking from S to T, that vertex we call as key vertex. Now you are given a directed graph, S and T, and you should tell us how many key vertexes are there in the graph.
Please notice that S and T are key vertexes and if S cannot walking to T by the directed edge in the initial graph then all vertexes becomes to key vertexes.
 

Input
The input consists of multiply test cases. The first line of each test case contains two integers, n(0 <= n <= 100000), m(0 <= m <= 300000), which are the number of vertexes and the number of edge. Each of the next m lines consists of two integers, u, v(0 <= u, v < n; u != v), indicating there exists an edge from vertex u to vertex v. There might be multiple edges but no loops. The last line of each test case contains two integers, S, T(0 <= S, T < n, S != T).

 

Output
Output the number of key vertexes in a single line for each test case.
 

Sample Input
6 6 0 1 1 2 1 3 2 4 3 4 4 5 0 5
 

Sample Output
4
 

Author
momodi
 

Statistic | Submit | Clarifications | Back