Problem A. Tank business ≡

Statement

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.

Input file format

Output file format

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.

Constraints

Sample tests

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

1 4 1

3 3 2
1 2
3 2
1 2
1
3 

-1 1

Problem B. Uncertain Finish ≡

Statement

At the running contest, jury used a new computerized stopwatch system to ensure the most accurate measuring of results. Unfortunately, despite very successfull trials, the system malfunctioned during the actual contest.

Jury was so confident in the new system that it did not use the old mechanical stopwatches. So the only way to determine outcome was to compare visual impressions of the people watching the contest. M such impressions were recorded, each in one of two forms: "runner A finished before runner B" and "runners A and B finished at the same time".

You task is to assign a place p_i to each of N runners, such that

1. If there is a record that A and B finished at the same time, then p_A = p_B.
2. If there is a record that A finished before B, then p_A < p_B.

Additionally, places must be allocated as densely as possible, i.e. 1 ≤ p_i ≤ K for minimum possible value of K.

Input file format

Output file format

Constraints

Sample tests

3 2
3 2 1
2 1 0

2 2 1

Problem C. Bipartite graph ≡

Statement

For a given undirected graph with N vertices and M edges you need to figure out whether the graph is bipartite or no.

NOTE. A graph is called bipartite if it's possible to split its vertices into two non-empty sets so that there is no edges between any two vertices from the same set.

Input file format

Output file format

Constraints

Sample tests

3 2
1 2  1 3

BIPARTITE

4 6
1 2  2 3  3 4  4 1  1 3  2 4

NO