#arc148c. [arc148_c]Lights Out on Tree
[arc148_c]Lights Out on Tree
Problem Statement
We have a rooted tree with vertices numbered to . Vertex is the root, and the parent of vertex is vertex .
There are coins with heads and tails, one on each vertex.
Additionally, there are buttons numbered to . Pressing button flips all coins on the vertices in the subtree rooted at vertex .
Process queries described below.
In the -th query, you are given a vertex set of size : $S_i = \\lbrace v_{i,1}, v_{i,2},\\dots, v_{i,M_i} \\rbrace$.
Now, the coins on the vertices in are facing heads-up, and the others are facing tails-up. In order to make all coins face tails-up by repeatedly choosing a button and pressing it, at least how many button presses are needed? Print the answer, or if there is no way to make all the coins face tails-up.
Constraints
- $\\displaystyle \\sum_{i=1}^Q M_i \\leq 2 \\times 10^5$
- are pairwise different.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print lines. The -th line should contain the answer to the -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 , flipping the coins on vertices .
For the second query, you can satisfy the requirement in two button presses, which is the minimum needed, as follows.
- Press button , flipping the coin on vertex .
- Press button , flipping the coins on vertex .