C - Lights Out on Tree Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

頂点に 1 から N の番号がついた N 頂点の根付き木があります。頂点 1 が根で、頂点 i (2 \leq i \leq N) の親は頂点 P_i です。
表裏のあるコインが N 枚あります。コインは全ての頂点の上に 1 枚ずつ載っています。
また、1 から N までの番号がついた N 個のボタンがあります。ボタン n を押すと n を根とする部分木に含まれる頂点に載っている全てのコインが裏返ります。

以下で説明するクエリを Q 個処理してください。

i 番目のクエリではサイズ M_i の頂点集合 S_i = \lbrace v_{i,1}, v_{i,2},\dots, v_{i,M_i} \rbrace が与えられます。
今、S_i に含まれる頂点の上に載っているコインは表を、それ以外のコインは裏を向いています。ボタンを 1 つ選んで押すことを繰り返して、N 枚のコイン全てを裏向きにするには、最小で何回ボタンを押す必要がありますか？答えを出力してください。ただし、どのようにボタンを押しても N 枚のコイン全てが裏向きにならない場合は -1 を出力してください。

制約

  • 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} は互いに異なる
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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 番目のクエリの答えを出力せよ。

入力例 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

出力例 1

1
2
1
3
2
3

1 番目のクエリについて、以下に説明するようにボタンを 1 回押すことで条件を満たすことができて、これが最小です。

  • ボタン 1 を押す。頂点 1,2,3,4,5,6 に載っているコインが裏返る。

2 番目のクエリについて、以下に説明するようにボタンを 2 回押すことで条件を満たすことができて、これが最小です。

  • ボタン 4 を押す。頂点 4 に載っているコインが裏返る。
  • ボタン 2 を押す。頂点 2,4,5,6 に載っているコインが裏返る。

Score : 500 points

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.

Sample 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

Sample 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.