Description

Anna正在和一群朋友在玩捉迷藏游戏。这种游戏由若干人一起玩，其中一个人为“鬼”，其他人藏在N个房间，由鬼来找这些人。Anna想计算出N(2 <= N <= 20,000)个房间（编号为1……N）中她应该藏哪一间？

Anna知道“鬼”会从房间1开始找。所有房间被M条双向路连接M (1<= M <= 50,000)，这种双向路以（A_i，B_i）表示，其中1<=A_i<=N;1<=B_i<=N; A_i!=B_i。通过这些双向路，任意两个房间之间都可以到达。

Anna觉得离房间1最远的那个房间最安全（相邻两个房间之间的距离为1），请你帮Anna编写一个程序找出她应该躲在哪个房间。

Input Format

第一行为N和M;第2行至第M+1行，分别包含一条路（A_i,B_i）。

Output Format

仅有一行，包含三个整数I、J、K，分别表示Anna应该躲的房间号（如果有多解，输出编号最小的）、房间1到Anna躲的房间的距离、Anna可以躲的房间数目。

Sample

【输入样例】hideseek.in 6 7 3 6 4 3 3 2 1 3 1 2 2 4 5 2 【输出样例】hideseek.out 4 2 3 【样例说明】 房间4,5,6 均离起点的距离为2，我们选择4号房间。