Hoseok's Two Chickens

Interview

Time limit1sMemory limit512 MB

Summary

Choose two buildings in an undirected graph to place shops so that the sum over all buildings of twice the distance to the nearest shop is minimized, breaking ties lexicographically.

Level: Medium5 of 10
Topics: Graph, Shortest path, Brute force, Implementation
Solved: No attempts yet

Problem

Computer science graduates are destined to run chicken shops. Don't deny reality; accept it and you'll feel better. In the end, even Hoseok runs a chicken shop in 2050. The shop is called "Hoseok's Two Chickens."

Having secured a branch in Kitchen City, Hoseok's Two Chickens plans to build 2 stores in the city. The city consists of N buildings and M roads. The buildings are numbered 1 through N. The i-th road connects two distinct buildings Ai and Bi and can be traveled in both directions in 1 hour.

We want to pick 2 buildings in Kitchen City to open chicken shops. We can't open them just anywhere, so we want to minimize the sum of accessibility over all buildings. The accessibility of building X is the shortest round-trip time from X to the nearest Hoseok's Two Chickens store. That is, we want to choose 2 buildings that minimize the "total shortest round-trip time from every building to the nearest chicken shop."

Hoseok graduated in computer science more than 30 years ago and no longer knows how to solve this problem by coding. For this washed-up algorithmist Hoseok, output the numbers of the 2 buildings that can be the optimal locations and the corresponding "total shortest round-trip time from every building to the nearest chicken shop." If there are multiple such building pairs, the pair with the smaller smaller-number is better; if the smaller numbers are equal, the pair with the smaller larger-number is better.

Input

The first line gives the number of buildings N and the number of roads M. The next M lines give the road information Ai, Bi separated by spaces. No road is given twice. It is guaranteed that for any two buildings, a route along the roads exists between them.

Output

On one line, output the numbers of the 2 buildings where the chicken shops will be built in ascending order, followed by the sum of round-trip times from all cities at that time.

If multiple building pairs are possible, output the one with the smaller smaller-number; if the smaller numbers are equal, output the one with the smaller larger-number.

Constraints

2 ≤ N ≤ 100
N-1 ≤ M ≤ N×(N - 1)/2
1 ≤ Ai, Bi ≤ N (Ai ≠ Bi)

Examples1

Example 1
Input
```
5 4
1 3
4 2
2 5
3 2
```
Expected output
```
1 2 6
```