Hide and Seek

Jaeseo is playing hide-and-seek with Suhyeon on a country farm. The farm has many barns, and Jaeseo must hide in one of them. There are $N$ barns in total, numbered from $1$ to $N$ ($2 \le N \le 20{,}000$).

Jaeseo knows that Suhyeon always starts searching from barn $1$. All barns are connected by $M$ bidirectional paths ($1 \le M \le 50{,}000$), and each path joins two distinct barns $A_i$ and $B_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$). From any barn, every other barn is always reachable.

Because Jaeseo's feet smell terrible, he wants to hide where the smell is least noticeable. The smell fades the farther a barn is from barn $1$, where distance is the minimum number of paths that must be traversed between two barns. In other words, the barn farthest from barn $1$ is the best hiding spot. Help Jaeseo find the barn to hide in!

The first line contains the number of barns $N$ and the number of paths $M$, separated by a space.

Each of the next $M$ lines contains two barn numbers $A_i$ and $B_i$, separated by a space, describing one path.

Print three values on a single line, separated by spaces.

• First value: the number of the barn to hide in (the barn whose distance from barn $1$ is the largest; if several barns share this largest distance, print the smallest such barn number).
• Second value: the distance to that barn.
• Third value: the number of barns that share this maximum distance.

A bird's-eye view of the farm is shown below.

1--2--5
| /|
|/ |
3--4
|
6

Barns $4$, $5$, and $6$ are all at distance $2$ from barn $1$. Barn $4$ is chosen among them because it has the smallest number.