Задача №3773. Родословная: LCA
В генеалогическом древе определите для двух элементов их наименьшего общего предка. Наименьшим общим предком элементов A и B является такой элемент C, что С является предком A, C является предком B, при этом глубина C является наибольшей из возможных. При этом элемент считается своим собственным предком.
Входные данные
Формат входных данных аналогичен предыдущей задаче.
Выходные данные
Для каждого запроса выведите наименьшего общего предка данных элементов.
Примечание
По-английски такая задача называется lowest common ancestor (LCA).
Примеры
Входные данные
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I Alexander_I Nicholaus_I Peter_II Paul_I Alexander_I Anna
Выходные данные
Paul_I Peter_I Anna
Сдать: для сдачи задач необходимо войти в систему