LCA офлайн

3000 мс · 32 МБ · всё или ничего

Полмиллиона вершин, полмиллиона запросов, тридцать два мегабайта. Запросы даны в явном виде.

Формат ввода

В первой строке $n$ и $q$ ( $1 \le n \le 5 \cdot 10^5$ , $1 \le q \le 5 \cdot 10^5$ ). Во второй строке $n-1$ родителей. В следующих $q$ строках пары вершин.

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

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

Примеры

ввод

вывод

1
0
0

ввод

1 1

0 0

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.