21989_MilitaryBases

There are N cities in a country. Some of the cities are connected by one-way roads that do not intersect outside the cities due to a system of bridges and tunnels. It is known that if there are direct roads from cities B and C to city A, then there is also a direct road either from B to C or from C to B. It is additionally known that is it not possible to start from a city and return to the same city after travelling the roads in some way.

As a part of more general reforms, the head of the state has decided to relocate military bases in the country. He knows that the international community would be alarmed if he would locate any two bases in cities connected by a direct road. He has asked you to help him to find a way to allocate as much military bases as possible without alarming the community.

The first line contains N (1 ≤ N ≤ 100000), the number of cities, and M (0 ≤ M ≤ 100000), the number of roads. Each of the following M lines contains two distinct integers from the range 1…N, the numbers of the cities a road connects (we assume the road goes from the first city of the pair to the second). It may be assumed that no two roads connect the same cities and that also the condition described above holds.

The first line of the output should contain K, the maximal number of cities where the bases could be located. The second line should  contain K integers, separated by single spaces, the numbers of cities where the bases should be located. Cities can be listed in any order. If there are several allocation plans with the maximal number of bases, output any one of them.

5 7
1 2
1 5
2 4
3 1
3 2
3 5
5 2

2
3 4