Tiny and Large Nodes

Let G be a simple connected undirected graph with N nodes which are labeled by integers 0, 1, 2, ..., N−1.
The degree of a node v is equal to the number of nodes which are adjacent to v.
The grade of a node v is equal to the sum of degrees of all nodes which are adjacent to v.
The tiny node T in the graph is defined as follows:
1. The grades of all nodes in the graph are bigger than or equal to the grade of T.
2. If a node v is different from T and the grades of v and T are equal, then the label of v is bigger than the label of T.
The large node L in the graph is defined as follows:
1. The grades of all nodes in the graph are less than or equal to the grade of L.
2. If a node v is different from L and the grades of v and L are equal, then the label of v is smaller than the label of L.

The distance between two nodes v and w is equal to the number of edges in a shortest path from v to w.

     

Image 1. Three graphs corresponding to Example 1, 2, and 3 below. The node grades are indicated in black at each node. The tiny and the large nodes in each graph are highlighted and marked by letter T and L, respectively. The distances between tiny and large nodes are: a) 2, b) 2, c) 4.

The task

Determine the labels of the tiny and the large node in the given graph and compute the distance between these two nodes.

---

Input

The first input line contains two integers N and M separated by space. The values indicate (in this order) the number of nodes and the number of edges in the input graph. The nodes are labeled by integers 0, 1, ..., N−1. Next, there are M text lines, each describe one edge. The line contains the labels of the edge end nodes separated by space. The order of nodes in the edge description and the order of edges in the input is arbitrary.
It holds, 2 ≤ N ≤ 10⁴, 1 ≤ M ≤ 10⁵.

Output

The output contains one text line with three integers T, L, D separated by spaces. They indicate (in this order) the label of the tiny node, the label of the large node and the distance between the tiny node and the large node in the input graph.

Example 1

Input

11 20
0 1
2 3
4 5
5 6
6 7
8 9
9 10
0 2
2 5
5 8
1 3
3 6
6 9
7 10
0 3
2 4
3 7
4 8
5 9
6 10

Output

1 6 2

The graph in Example 1 is depicted in Image 1 a).

Example 2

Input

10 9
0 4
1 4
2 4
3 4
4 5
5 7
5 8
5 9
5 6

Output

0 5 2

The graph in Example 2 is depicted in Image 1 b).

Example 3

Input

15 17
0 1
6 7
7 8
13 14
3 6
6 9
2 4
7 10
10 12
5 8
8 11
0 2
1 2
2 6
8 12
12 13
12 14

Output

3 12 4

The graph in Example 3 is depicted in Image 1 c).

---

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set