URI Online Judge | 1698

Brazilian Metro

By Caique Porto Lira, ITA BR Brazil

Timelimit: 1

A big earthquake has destroyed the whole São Paulo's metro system, but Brazil is going to be the host for the World Cup, so the Government has taken two measures: The first is to buy a teletransport system between two metro stations, the second is to, in order to avoid unnecessary costs, rebuild some of the metro routes so that there is exactly one path between each pair of metro stations. A configuration is any metro system that can be a result of the Government's measures. Given the old metro system, determine the pair of stations that, when connected by the teletransport system, can result in the maximal number of configurations.

Input

The input contains several test cases and ends with end-of-file (EOF).

The first line of each test case consists of two integers N and M (1 < N <= 12 and N - 1 <= M <= N*(N - 1)/2). The next M lines contain each two integers A and B (0 <= A,B<= N - 1), meaning that stations A and B were connected before the earthquake.

Output

For each test case, the output consists of two integers A and B (A < B), denoting the two stations that should be connected by the teletransport system in order to maximize the number of possible configurations. In case of multiple answers, print the lexicographically lowest.

Sample Input Sample Output

6 6

0 1

0 2

1 2

0 3

1 4

2 5

3 4