Fire safety#1937
In city X, there are houses. Some of them are connected by one-way roads.
Recently, the number of fires in city X has increased. To address this problem, the residents decided to build several fire stations in the city. However, a difficulty arose: when responding to an emergency, a fire truck may ignore the direction of the roads, but on the way back it must strictly follow all traffic rules (the residents of city X observe them rigorously!).
It is necessary to ensure that, regardless of its current location, a fire truck can always return to the same fire station from which it departed. Since building fire stations is costly, the city council decided to construct the minimum possible number of stations that satisfy this condition. In addition, in order to reduce costs, fire stations may only be built next to existing houses.
Write a program that determines the optimal placement of fire stations.
The first line contains the number of houses n~(1 \le n \le 3000).
The second line contains the number of roads m~(1 \le m \le 10^5).
Each of the following lines describes a road in the format a_i~b_i, which means that it is possible to travel along the -th road from house a_i to house b_i~(1 \le a_i, b_i \le n).
In the first line, print the minimum number of fire stations that need to be built. In the second line, print integers in any order — the indices of the houses next to which the fire stations should be built.
If there are multiple optimal solutions, print any of them.
Example 1