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

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
2
1
3
2
3

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

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

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

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