| Codeforces Global Round 17 |
|---|
| Закончено |
После просмотра нового сериала «Игра в кальмара» Маштали и Соруш решили провести свою собственную «Игру в кальмара»! Соруш согласился быть ведущим и предоставить деньги для приза победителю, а Маштали стал фронтменом!
$$$m$$$ игроков зарегистрировались для участия в играх, чтобы выиграть большой приз, но когда Маштали узнал, каким огромным будет приз победителя, он решил убить устранить всех игроков, чтобы забрать деньги себе!
Вот как злой Маштали собирается уничтожить игроков:
Дано некорневое дерево с $$$n$$$ вершинами. У каждого игрока есть $$$2$$$ специальные вершины $$$x_i$$$ и $$$y_i$$$.
За одну операцию Маштали может выбрать любую вершину $$$v$$$ дерева. Затем для каждого оставшегося игрока $$$i$$$ он находит вершину $$$w$$$ на простом пути из $$$x_i$$$ в $$$y_i$$$, которая ближе всего к $$$v$$$. Если $$$w\ne x_i$$$ и $$$w\ne y_i$$$, игрок $$$i$$$ будет устранен.
Теперь Маштали задался вопросом: «Какое минимальное количество операций я должен выполнить, чтобы устранить всех игроков и забрать деньги себе?».
Поскольку он думал только о деньгах, он не смог решить задачу самостоятельно и обратился к вам за помощью!
Первая строка содержит $$$2$$$ целое число $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 3 \cdot 10^5)$$$ — количество вершин дерева и количество игроков.
Вторая строка содержит $$$n-1$$$ целых чисел $$$par_2, par_3, \ldots, par_n$$$ $$$(1 \le par_i < i)$$$ — обозначающих ребро между вершиной $$$i$$$ и $$$par_i$$$.
В $$$i$$$-й из следующих $$$m$$$ строк содержится два целых числа $$$x_i$$$ и $$$y_i$$$ $$$(1 \le x_i, y_i \le n, x_i \ne y_i)$$$ — специальные вершины $$$i$$$-го игрока.
Выведите минимальное количество операций, которые Маштали должен выполнить.
Если Маштали никак не может устранить всех игроков, выведите $$$-1$$$.
6 3 1 1 1 4 4 1 5 3 4 2 6
2
5 3 1 1 3 3 1 2 1 4 1 5
-1
Пояснение к первому примеру:
В первую операцию, Маштали может выбрать вершину $$$1$$$ и устранить игроков с красным и синим цветами. Во второй операции он может выбрать вершину $$$6$$$ и устранить игрока с оранжевым цветом. Во втором примере Маштали не сможет устранить первого игрока.
