EduBrick

Самая далёкая вершина

8000 мс · 256 МБ · всё или ничего

Найдите вершину, до которой от вершины 1 идти дальше всего. Если таких несколько, выведите наименьший номер. Недостижимые вершины не считаются.

Формат ввода

В первой строке числа nn от 11 до 21052 \cdot 10^5 и mm от 00 до 21052 \cdot 10^5. Во второй строке 2m2m чисел: пары концов рёбер.

Формат вывода

Два числа через пробел: номер вершины и расстояние.

Примеры

ввод
2 1
1 2
вывод
2 1
Войдите, чтобы отправлять решения.