No tags yet

No tag edit access

Time limit per test: 1 second(s)

Memory limit: 262144 kilobytes

Memory limit: 262144 kilobytes

input: standard

output: standard

output: standard

Governments of different countries like to boast about their achievements. For instance, the President of Flatland has announced that his country has the most advanced road system. He said the degree of a country road system development is equal to the amount of cities in the largest subset of cities. A subset of cities is called if it is possible to get from any city of the subset to all other cities of the subset.

Not to lag behind the neighbors Berland's President decided to undertake a reform and modernize roads in his country. All the roads in Berland are one-way, each of them connects a pair of cities in one direction. There is at most one road in each direction between any two given cities.

Since there is little money in the budget, President's plans aren't very ambitious. He can turn at most one of all given one-way roads into a two-way road. And he wants to do it in such a way that the resulting road system degree of development in Berland becomes as high as possible. Let's say the maximum degree of development, which can be achieved by this action, is equal to

A road is called if, after it is changed from one-way to two-way, the degree of road system development becomes equal to

sample input | sample output |

5 4 1 2 2 3 1 3 4 1 | 3 1 3 |

sample input | sample output |

3 4 1 2 2 1 1 3 3 1 | 3 4 1 2 3 4 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2020 18:15:16 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|