AT_arc148_c.[ARC148C] Lights Out on Tree

有一棵有 $N$ 个顶点的有根树，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根节点，对于每个 $i$ $(2 \leq i \leq N)$，顶点 $i$ 的父节点是顶点 $P_i$。

每个顶点上放有一枚正反两面的硬币，共 $N$ 枚。

此外，有 $N$ 个编号为 $1$ 到 $N$ 的按钮。按下按钮 $n$ 时，以 $n$ 为根的子树内所有顶点上的硬币都会被翻面。

现在需要处理 $Q$ 个如下描述的查询。

对于第 $i$ 个查询，给定一个大小为 $M_i$ 的顶点集合 $S_i = \{ v_{i,1}, v_{i,2}, \dots, v_{i,M_i} \}$。

此时，$S_i$ 中的顶点上的硬币为正面，其余顶点上的硬币为反面。你可以多次选择一个按钮按下，每次操作后所有被影响的硬币都会翻面。请问，最少需要按多少次按钮，才能使所有 $N$ 枚硬币都变为反面？如果无论如何都无法全部变为反面，请输出 $-1$。

输入按以下格式从标准输入读入。

$N$ $Q$
$P_2$ $P_3$ $\dots$ $P_N$
$M_1$ $v_{1,1}$ $v_{1,2}$ $\dots$ $v_{1,M_1}$
$M_2$ $v_{2,1}$ $v_{2,2}$ $\dots$ $v_{2,M_2}$
$\vdots$
$M_Q$ $v_{Q,1}$ $v_{Q,2}$ $\dots$ $v_{Q,M_Q}$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个查询的答案。

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq P_i < i$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq M_i$
• $\displaystyle \sum_{i=1}^Q M_i \leq 2 \times 10^5$
• $1 \leq v_{i,j} \leq N$
• $v_{i,1}, v_{i,2}, \dots, v_{i,M_i}$ 互不相同
• 所有输入均为整数

样例解释 1

对于第 $1$ 个查询，如下操作只需按 $1$ 次按钮即可满足条件，且这是最小次数。

• 按下按钮 $1$。顶点 $1,2,3,4,5,6$ 上的硬币被翻面。

对于第 $2$ 个查询，如下操作只需按 $2$ 次按钮即可满足条件，且这是最小次数。

• 按下按钮 $4$。顶点 $4$ 上的硬币被翻面。
• 按下按钮 $2$。顶点 $2,4,5,6$ 上的硬币被翻面。

由 ChatGPT 4.1 翻译