CF1610H Squid Game

在观看了新上映的高分剧集《鱿鱼游戏》后，Mashtali 和 Soroush 决定举办属于他们自己的“鱿鱼游戏”！Soroush 同意担任主持人，并为获胜者提供奖金，而 Mashtali 则成为了“前台人”！ 有 $m$ 名玩家报名参加游戏，争夺丰厚的奖金。但当 Mashtali 发现奖金数额巨大时，他决定消灭所有玩家，这样他就能独吞奖金！ Mashtali 消灭玩家的方式如下： 有一棵无根树，共有 $n$ 个结点。每个玩家有 $2$ 个特殊结点 $x_i$ 和 $y_i$。 每次操作中，Mashtali 可以选择树上的任意一个结点 $v$。然后，对于每一个尚未被淘汰的玩家 $i$，他会在 $x_i$ 到 $y_i$ 的简单路径上，找到距离 $v$ 最近的结点 $w$。如果 $w \ne x_i$ 且 $w \ne y_i$，那么第 $i$ 个玩家会被淘汰。 现在 Mashtali 想知道：“我最少需要进行多少次操作，才能将所有玩家都淘汰出局，从而独吞奖金？” 由于他只想着钱，自己解决不了这个问题，于是向你寻求帮助！

第一行包含两个整数 $n$ 和 $m$，表示树的结点数和玩家数，$1 \le n, m \le 3 \times 10^5$。 第二行包含 $n-1$ 个整数 $par_2, par_3, \ldots, par_n$，$1 \le par_i < i$，表示结点 $i$ 与 $par_i$ 之间有一条边。 接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$，$1 \le x_i, y_i \le n, x_i \ne y_i$，表示第 $i$ 个玩家的两个特殊结点。

输出 Mashtali 至少需要进行的操作次数。 如果无法将所有玩家都淘汰，输出 $-1$。

第一个样例的解释：  第一次操作，Mashtali 选择结点 $1$，可以淘汰红色和蓝色的玩家。第二次操作，他选择结点 $6$，可以淘汰橙色玩家。 在第二个样例中，Mashtali 无法淘汰第一个玩家。 由 ChatGPT 4.1 翻译