EduBrick

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

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

Неориентированный граф задан списком рёбер. Найдите вершину, наиболее удалённую от вершины xx, и это расстояние. Если таких вершин несколько, выведите наименьший номер.

Недостижимые вершины не рассматриваются.

Формат ввода

Первая строка содержит числа nn (1≤n≤1051 \le n \le 10^5), mm (0≤m≤2⋅1050 \le m \le 2 \cdot 10^5) и xx.

Далее идут mm строк с рёбрами.

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

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

Примеры

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