Problem L
Planes, Trains, but not Automobiles

Being a traveling salesman is tough work. Per is one such salesman and would like to find an efficient way to visit all the cities in a foreign country exactly once.

Per defines efficiency in a peculiar way as Per hates flying on planes. Even worse, he absolutely refuses to use automobiles. Per’s favorite mode of transportation is trains. He will gladly take trains for as long as possible.

The train system in this country is very peculiar, and very limited. Train lines are all one-way, and once anyone takes a train out of a city, there is no sequence of train lines that return to that city. This is because the country is trying to make money off of the more costly planes. In this country, every city has exactly one airport, so you can travel by plane from any city to any other city.

Per doesn’t just want to know the minimum number of flights he needs. He also wants to know in which cities he can visit the airport during some trip with fewest flights. Per likes airport restaurants, you see, and would like to know which restaurants he can visit, so he can choose his route to visit his favorites. He can visit the airport if he flies in or out of the city. Note that Per can start in any city.

Consider this country with four cities, with the arrows representing one-way train routes:

\includegraphics[width=0.15\textwidth ]{PTnoA.jpg}

There are several possible trips Per could take, but he’s going to need to fly at least once. Here are some (but not all) possible routes with fewest flights, with $\rightarrow $ indicating a train trip and $\Rightarrow $ indicating a flight:

$1 \rightarrow 2 \rightarrow 4 \Rightarrow 3$
$2 \rightarrow 4 \Rightarrow 1 \rightarrow 3$
$1 \rightarrow 3 \rightarrow 4 \Rightarrow 2$

In this example, every airport is visited on at least one of the routes. Per has the option to choose his route so he can visit any airport restaurant he wishes.


Each test case will begin with a line with two space-separated integers $n$ ($1\! \le \! n\! \le \! 10^5$) and $m$ ($0\! \le \! m\! \le \! 10^5$), where $n$ is the number of cities and $m$ is the number of train lines. The cities are numbered $1..n$.

Each of the next $m$ lines contains two space separated integers $a$ and $b$ ($1\! \le \! a,b\! \le \! n, a\! \neq \! b$), which indicates that there is a train line from city $a$ to city $b$ (but not back). All train lines will be distinct.


Produce exactly two lines of output.

On the first line, output a single integer, which is the minimum number of flights Per must take to visit all of the cities.

On the second line, output a list of space-separated integers, which are the cities with airports he can visit. If he can visit an airport on any one of the routes with the minimum number of flights, it should be listed. Output these numbers in increasing order. If no airports are to be visited, output a blank line.

Sample Input 1 Sample Output 1
4 4
1 2
1 3
2 4
3 4
1 2 3 4
Sample Input 2 Sample Output 2
4 3
1 2
2 3
3 4

Please log in to submit a solution to this problem

Log in