| Author: | T. Chistyakov, A. Klenin | Time limit: | 5 sec | |
| Input file: | input.txt | Memory limit: | 1 Mb | |
| Output file: | output.txt |
The Tank World consists of several countries. Pease treaties are signed between some pairs of countries. If two countries don't have a peace treaty signed between them, they potentially can start a war against each other.
The countries in the Tank World are very small, and some of them have Military Factories, but none of them has more than one Military Factory. Each Military Factory produces tanks (there is no other weapon in the Tank World). As the countries are very small, the Military Factories are also small, and always produce one tank a year.
If two countries have a peace treaty signed between them, they totally trust each other and support each other in the case when one of them is in war with some other counry. In particular, if there is a Military Factory in a country, this country can sell the tank this Factory produces to some other peaceful country that doesn't have its own Factory. Nobody ever sells a tank to a country without prior signing a peace treaty with that country.
You represent Tank World United Nations. You believe that the less tanks is overall sold, the more peaceful the Tank World is. Also you know, that the more countries don't have peace treaties between them, the less tanks can potentially be sold.
As a representative of Tank World United Nations, you personally know leaders of all the countries. That is why you can incline any pair of countries that have a peace treaty between them to cancel this treaty. However, you can do it only once, as if you do it too often, people will not trust Tank World United Nations anymore.
Your task is complicated by the fact, that after the peace treaty is cancelled, tank producing country can sell its tank to some other country (and it will do it if possible — tank business is very profitable, and usually businessmen don't really believe that a war can start).
Let's formalize the task. There are N countries in the Tank World. There exist M peace treaties between them. P countries produce tanks. Your goal is to find one peace treaty that can be cancelled, and the maximum number of tanks that can be sold if this treaty is cancelled.
Output file must contain numbers x y, describing a peace treaty between countries x and y that needs to be cancelled to minimize the maximum number of potentially sold tanks, x < y. If several solutions exist, display the one of them having the minimum x. If cancelling of any treaty doesn't make things any better, output -1.
After that output the maximum number of tanks that will be sold if the peace treaty is cancelled. Output this number even if there is no reason to cancel any peace treaty.
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|