|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
2006. Genealogic Tree
|
| View Problem Statistics | Submit | Problem added debug |
|
Как-то раз одна большая семья решила узнать побольше о своих предках и дальних родственниках. Покопавшись в архивах, им удалось найти сведения об n людях, которые, возможно, имеют с ними родственные связи (включая даже тех, кто жил несколько веков назад). Конечно, полной информации найти не получилось, поэтому для каких-то людей известны оба родителя, для кого-то – только один, а для кого-то сведений о родителях и вовсе не нашлось. Полученные данные были представлены в виде графа. Вершины графа представляют людей. Направленное ребро, идущее от вершины u к вершине v, означает, что человек с номером u является родителем v. В каждую вершину входит не более двух рёбер. Гарантируется, что циклов в графе нет. Назовём степенью кровного родства между людьми u и v минимальную длину неориентированного пути между ними, проходящего через их общего предка. Примечание: при этом будем считать, что каждая вершина является предком самой себе. Например, на следующем рисунке для людей 5 и 6 степень родства равна 3 (поскольку кратчайший путь, проходящий через их общего предка, содержит три ребра). Для людей 6 и 3 ответом будет 2, поскольку с учётом примечания их общий предок – это вершина 3, и кратчайший путь содержит 2 ребра.  Напишите программу, которая определит степень кровного родства для заданных пар людей. Входные данные В первой строке входных данных записано целое число n – количество людей (2 ≤ n ≤ 104). В следующих n строках записана информация о родителях каждого человека: вначале идёт число 0, 1 или 2 – количество известных родителей, после чего через пробел записаны номера родителей. В следующей строке записано целое число q – количество пар людей, для которых надо определить степень кровного родства (1 ≤ q ≤ 5·105). В следующих q строках содержатся пары целых чисел – номера людей. Выходные данные Выведите q целых чисел – степень кровного родства для каждой пары людей из входных данных. Если у какой-то пары нет общих предков, то выведите -1. Пример Входные данные 6 0 0 1 1 2 2 3 2 2 3 1 4 3 5 6 6 3 2 3 Выходные данные 3 2 -1 |
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Vologda Students Contests / | XXII Interuni Olympiad - 2019 / |
| 2005. F - Space Characters | 2006. | 2007. H - Beautiful Numbers | 2008. I - Saddle Point | 2009. J - Copy-Paste |
| time generating 0.141 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |