숨바꼭질

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 여러 개 있으며, 재서기는 그 중 하나에 숨어야 한다. 헛간은 모두 $N$개이고 $1$번부터 $N$번까지 번호가 매겨져 있다 ($2 \le N \le 20{,}000$).

재서기는 수혀니가 항상 $1$번 헛간부터 찾기 시작한다는 것을 알고 있다. 모든 헛간은 $M$개의 양방향 길로 이어져 있으며 ($1 \le M \le 50{,}000$), 각 길은 서로 다른 두 헛간 $A_i$와 $B_i$를 잇는다 ($1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$). 어떤 헛간에서 출발하더라도 다른 모든 헛간에 반드시 도달할 수 있다.

재서기는 발 냄새가 지독하기 때문에 냄새가 최대한 나지 않는 곳에 숨으려고 한다. 냄새는 $1$번 헛간에서 멀어질수록 옅어지며, 여기서 거리란 두 헛간을 오갈 때 지나야 하는 길의 최소 개수를 뜻한다. 즉, $1$번 헛간에서 가장 먼 헛간이 숨기에 가장 좋은 장소다. 재서기가 숨을 헛간을 찾을 수 있게 도와주자!

첫째 줄에 헛간의 개수 $N$과 길의 개수 $M$이 공백으로 구분되어 주어진다.

이어지는 $M$개의 줄에는 각 길이 잇는 두 헛간의 번호 $A_i$와 $B_i$가 공백으로 구분되어 주어진다.

한 줄에 세 개의 값을 공백으로 구분하여 출력한다.

• 첫 번째 값: 숨어야 하는 헛간의 번호 ($1$번 헛간에서의 거리가 가장 먼 헛간이며, 그러한 헛간이 여러 개라면 번호가 가장 작은 것을 출력한다).
• 두 번째 값: 그 헛간까지의 거리.
• 세 번째 값: 그 최대 거리와 같은 거리를 갖는 헛간의 개수.

아래는 농장의 조감도이다.

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

헛간 $4$, $5$, $6$은 모두 $1$번 헛간에서의 거리가 $2$로 같다. 이 중에서 $4$번 헛간을 고르는 이유는 번호가 가장 작기 때문이다.