3205：Ikki's Story II - War with TN

Do you remember the war of my nation with TN?

If you don’t know that story, ask frkstyc to tell you. (And frkstyc says, “Please don’t ask me but refer to problem 2822 TN’s Kingdom IV – Collapse.”)

Once upon a time, I defeated the evil nation of TN! How did I do that?

Simple! The road network of the country of TN could be viewed as a directed graph, where each city is a vertex and there are edges between cities. And the capital s, is a distinguished vertex and every other vertex is reachable from s.

Well, let me see what happened at that time…

I wanted to destruct one particular city, t of the evil nation of TN. Since if I wanted to destroy t, TN would send troops from s to t to defend his nation. So I wanted to destroy all the cities (except s and t) that satisfy the following property:

All the paths from s to t would pass this city.

If all the cities with this property were destroyed and controlled by me, it would be quite certain that TN’s troops could not reach city t! Then it would be quite true that I would destroy city t relatively safely. :)

The evil nation was defeated because Ikki himself solved this problem! If you were Ikki, can you also solve this problem?

The input contains exactly one test case.

The first line of the test case contains two integers N, M (N ≤ 10,000, M ≤ 100,000) which represent the number of cities and roads in the nation of TN, respectively.

M lines follow, each line contains two integers a, b, which means that there was a road from city a to city b (0 ≤ a, b < N). All the roads were directional.

Cities are numbered from 0 to N − 1, the capital is numbered 0.

The last line of each test case is an integer t, which is the city that Ikki was going to destroy.