EduBrick

Общий предок множества

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

Каждый запрос — набор вершин. Найдите их общего предка наибольшей глубины.

Формат ввода

В первой строке nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5), во второй — n−1n-1 родителей. Далее qq (1≤q≤1051 \le q \le 10^5); каждый из следующих qq запросов задан строкой: сначала kk (1≤k≤n1 \le k \le n), затем kk номеров вершин. Суммарное kk не превосходит 5⋅1055 \cdot 10^5.

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

Для каждого запроса выведите номер общего предка набора.

Примеры

ввод
5
0 0 1 1
2
2 3 4
3 3 4 2
вывод
1
0
ввод
1

1
1 0
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.