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 of each case
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.
each case should contain K, the
maximal number of cities where the bases could be located.
5 7 1 2 1 5 2 4 3 1 3 2 3 5 5 2
2
Migrated from old NTUJ.
icpc2008, neerc west
| No. | Testdata Range | Score |
|---|