AtCoder Regular Contest 148
C
Lights Out on Tree
AtCoder
⌀ 1488
原题
← BD →
翻译中…

Problem Statement

翻译中…

We have a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ is vertex $P_i$. There are $N$ coins with heads and tails, one on each vertex. Additionally, there are $N$ buttons numbered $1$ to $N$. Pressing button $n$ flips all coins on the vertices in the subtree rooted at vertex $n$.

翻译中…

Process $Q$ queries described below.

翻译中…

In the $i$-th query, you are given a vertex set of size $M_i$: $S_i = \lbrace v_{i,1}, v_{i,2},\dots, v_{i,M_i} \rbrace$. Now, the coins on the vertices in $S_i$ are facing heads-up, and the others are facing tails-up. In order to make all $N$ coins face tails-up by repeatedly choosing a button and pressing it, at least how many button presses are needed? Print the answer, or $-1$ if there is no way to make all the coins face tails-up.

翻译中…

Constraints

翻译中…
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq P_i \lt 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}$ are pairwise different.
  • All values in the input are integers.
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

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}

翻译中…

Output

翻译中…

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.

翻译中…

样例

Input #1
6 6
1 1 2 2 5
6 1 2 3 4 5 6
3 2 5 6
1 3
3 1 2 3
3 4 5 6
4 2 3 4 5
Output #1
1
2
1
3
2
3
For the first query, you can satisfy the requirement in one button press, which is the minimum needed, as follows. - Press button $1$, flipping the coins on vertices $1,2,3,4,5,6$. For the second query, you can satisfy the requirement in two button presses, which is the minimum needed, as follows. - Press button $4$, flipping the coin on vertex $4$. - Press button $2$, flipping the coins on vertex $2,4,5,6$.
题目信息
题号
arc148_c
时间限制
3 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。