Напишите программу, которая принимает на вход корневое дерево и список пар вершин. Для каждой пары ($$$u,v$$$) программа определяет ближайшего общего предка $$$u$$$ и $$$v$$$ в дереве. Ближайший общий предок двух узлов $$$u$$$ и $$$v$$$ — это узел $$$w$$$, который является предком как $$$u$$$, так и $$$v$$$, и имеет наибольшую глубину в дереве. Узел может быть своим собственным предком (например, на Рисунке 1 предками узла 2 являются 2 и 5).
Набор данных, который считывается из текстового файла, начинается с описания дерева в следующем формате:
количество_вершин
вершина:(количество_потомков) потомок1 потомок2 ... потомокn
…
где вершины представлены в виде целых чисел от 1 до $$$n$$$. Описание дерева сопровождается списком пар вершин в формате:
количество_пар
(u,v)
(x,y)
…
Входной файл содержит несколько наборов данных (как минимум один). Обратите внимание, что пробелы (табуляции, пробелы и разрывы строк) могут свободно использоваться во входных данных.
Для каждого общего предка программа выводит предка и количество пар, для которых он является предком. Результаты выводятся на стандартный вывод на отдельных строках в порядке возрастания вершин в формате:
предок:количество
Например, для следующего дерева:
входные и выходные данные программы:
Ввод состоит из нескольких наборов данных. Каждый набор данных начинается с описания дерева, за которым следует список пар вершин. Дерево описывается количеством вершин и для каждой вершины указывается количество потомков, за которым следует список потомков. Список пар описывается количеством пар, за которым следуют сами пары.
Для каждой пары выведите ближайшего общего предка и количество пар, для которых он является предком, в формате: предок:количество. Результаты должны быть выведены в порядке возрастания вершин.
5 5:(3) 1 4 2 1:(0) 4:(0) 2:(1) 3 3:(0) 6 (1,5) (1,4) (4,2) (2,3) (1,3) (4,3)
2:1 5:5