Дано дерево, представленное в виде списка ребер. Каждое ребро соединяет две вершины, и каждая вершина имеет уникальный идентификатор. Необходимо выполнить несколько операций на дереве, включая поиск расстояния между двумя вершинами и нахождение их общего предка.

Условия задачи:

• Вводится список ребер, каждое ребро — это пара чисел, обозначающих вершины, которые соединяет данное ребро.
• Известно, что дерево — это связный ациклический граф.
• Для каждой пары вершин нужно найти их общий предок.
• Для каждой пары вершин нужно вычислить расстояние между ними, которое равно числу рёбер на кратчайшем пути между этими вершинами.

Входные данные:

• Сначала вводится число вершин n.
• Далее идет n-1 строк, каждая из которых содержит пару чисел, обозначающих вершины, соединенные ребром.

Выходные данные:

• Для каждой пары вершин необходимо вывести их общий предок и расстояние между ними.

Пример:

Вход:

5
1 2
1 3
3 4
3 5
2 4

Выход:

1 2
1 3

Объяснение:

• В данном примере дерево состоит из 5 вершин и 4 рёбер. Ответы на запросы о расстоянии и общем предке для каждой пары вершин будут вычисляться на основе структуры дерева.