In Berland, a prosperous country, there are n nice cities, some of which are connected by one-way roads. Berland has a constant and long-standing enemy - Birland, with which it has been in war for many years. Birland's military leaders have understood that they can't defeat Berland by fair means, and they've chosen the way of sabotage. One of the planned acts of sabotage is to kill the King of Berland.
The King lives in his palace in the country's capital (city with index s), but it's impossible to penetrate into it by any means. However, they've got to know that soon the King is going to city with index t to in augurate a chocolate factory. In city t unprecedented security measures have also been taken. So, it's not possible to kill the King there. The military leaders have found out that the King is going to stop in each city on his path to city t to speak to the people. The leaders came to the conclusion that during one of such speeches it's very convenient to assassinate the King. But the route of the King's trip is kept secret, thus, they don't know in which city to prepare the attempt on the King's life. Having thought for a while, they've taken the decision to choose one of the cities that the King is going to pass anyway. Your task is to fi nd all such cities.
You may assume that there is always at least one path from s to t.
Input consists of multiple blocks of test cases, and is ended with EOF. Each block consists of the following:
The first line contains four integers: n, m, s and t (2 ≤ n ≤ 100000, 1 ≤ m ≤ 300000, 1 ≤ s, t ≤ n, s != t). The following m lines each contain two integers xi and yi -- indices of the cities connected by the i-th
road in order of the road direction (1 ≤ xi , yi ≤ n, xi != yi ). Each pair of different cities is connected by
at most one road in each direction.
For each test case output two lines: (even if the second line is empty)
In the first line, output the number of cities k which the King should pass anyway. In the second line, output k space-separated numbers -- indices of these cities. Output the cities in increasing order of their indices.
4 3 1 4 1 2 2 3 3 4 4 4 1 4 1 2 2 3 3 4 1 3 4 5 1 4 1 2 2 3 3 4 1 3 2 4
2 2 3 1 3 0
Migrated from old NTUJ.
Petrozavodsk training camp, 2011
| No. | Testdata Range | Score |
|---|