Relaxed Edges

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.
A node v is a relaxed node if the number of nodes adjacent to v which have the same degree as v is less than one third of the degree of v.
An edge is a relaxed edge if both its end nodes are relaxed nodes.
Let v and w be the labels of end nodes of an edge e and let v<w. The label of e is defined as the integer v×N+w. Note that the labels of all edges in G are pairwise different.

The distance between two edges e and f is the minimum possible length of a path which connects one of the end nodes of e to one of the end nodes of f.

   


Image 1. Three graphs corresponding to Example 1, 2, and 3 below. The edge labels are indicated in black at each edge. The relaxed nodes in the graphs are: a) 0, 1, 2, 3, 5, 9, b) all nodes, c) all nodes except 0, 1, 13, 14.
The end nodes of the relaxed edges with minimum and maximum labels are highlighted, blue and black correspond to minimum and maximum, respectively. The distances between these two edges are: a) 2, b) 1, c) 3.

The task

In the given graph, find a relaxed edge with the minimum label and a relaxed edge with the maximum label. Determine the distance between these two edges.

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 describes 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 ≤ 104, 1 ≤ M ≤ 105.

Output

The output contains one text line with three integers A, B, D separated by spaces. They indicate (in this order) the minimum label of a relaxed edge, the maximum label of a relaxed edge and the distance between these two edges 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 64 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
4 59 1
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
34 162 3
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