2011 Зимняя Школа, Харьков, День 8, День Виталия Гольдштейна

Fire safety

There are n houses in the city of Zelenograd. Some of them are connected by one-way roads.

In recent times in Zelenograd the incidents of fires have increased. In this regard, the residents decided to build several fire stations in the city. But there was a problem - the fire engine traveling on the call, of course, can ignore the direction of the current road, however, the car returning from the job is obliged to follow the traffic rules (the people of Zelenograd piously respect these rules!).

It is clear that wherever the fire truck will be, it should be possible to return to the fire station where from it started its way. But the construction of stations costs a lot of money, so at the city council it was decided to build a minimum number of stations in such a way that this condition was hold. In addition for saving money, it was decided to build stations in the form of extensions to existing houses.

Your task is to write a program that calculates the optimal position of the stations.


First line contains the number of houses n (1n3000). Second line contains the number of roads m (1m105). Then the description of the roads is given in format aibi meaning that it is allowed for the cars to move along the road i from the house ai to the house bi (1ai, bin).


In the first line print the minimum number of fire stations k that must be built. In the second line print k numbers in random order - the houses where you need to attach the fire stations. If there are several optimal solutions, output any.


Time limit 1 second
Memory limit 128 MiB
Input example #1
1 2
2 3
3 1
2 1
2 3
3 4
2 5
Output example #1
4 5
Author Vitaly Goldstein
Source 2011 Winter School, Kharkov, Day 9