Monochrome Levels - Repovive Premier Round 5 | Repovive

13F. Monochrome Levels

3000 pts4s512 MB

You are given a tree with $n$ vertices. The tree is rooted at vertex $1$ .

Each vertex is colored either blue or red. The color of vertex $i$ is denoted by $s_i$ .

For a vertex $v$ , consider the subtree of $v$ . For every integer $h \ge 0$ , look at all vertices in this subtree whose distance from $v$ is exactly $h$ . Vertex $v$ is called good if, for every such $h$ , all these vertices have the same color. A level with zero or one vertex always satisfies this condition.

You have to process $q$ queries. In each query, one vertex is given and its color is toggled: blue becomes red, and red becomes blue.

After each query, output the number of good vertices in the tree.

Constraints

$1 \le t \le 10^4$
$1 \le n, q$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $q$ over all test cases is at most $2 \times 10^5$
$s_i \in \{\texttt{B}, \texttt{R}\}$
The given edges form a tree
$1 \le x_i \le n$

Input

t

\left. \begin{array}{l} n \quad q \\ s \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \\ x_1 \\ x_2 \\ \vdots \\ x_q \end{array} \right\} \times t

Output

For each test case, after each query output one integer, the number of good vertices after applying that query.

\left. \begin{array}{l} a_1 \\ a_2 \\ \vdots \\ a_q \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Explanation

Case 1

There is only one vertex, so it is good after every color change.

Case 2

The tree is a path. For every vertex, each level inside its subtree contains at most one vertex, so all three vertices are always good.

Case 3

After the first change, all children of vertex 1 have the same color, so every vertex is good. After each later change, the children of vertex 1 do not all have the same color, so vertex 1 is not good, while all leaves are good.

Output

Case 1

1
1
1

Case 2

Case 3

Input

Case 1

Case 2

Explanation

Case 1

After the six changes, the sets of good vertices are respectively {4, 5, 6, 7, 8}, {2, 4, 5, 6, 7, 8}, {2, 3, 4, 5, 6, 7, 8}, {2, 4, 5, 6, 7, 8}, {2, 4, 5, 6, 7, 8}, and {2, 4, 5, 6, 7, 8}.

Case 2

After the seven changes, the sets of good vertices are respectively {2, 3, 4, 5, 6, 7, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {3, 5, 6, 7, 8, 9, 10}, {5, 6, 7, 8, 9, 10}, {5, 6, 7, 8, 9, 10}, and {5, 6, 7, 8, 9, 10}.

Output

Case 1

Case 2

You are given a tree with $n$ vertices. The tree is rooted at vertex $1$ .

Each vertex is colored either blue or red. The color of vertex $i$ is denoted by $s_i$ .

You have to process $q$ queries. In each query, one vertex is given and its color is toggled: blue becomes red, and red becomes blue.

After each query, output the number of good vertices in the tree.

$1 \le t \le 10^4$
$1 \le n, q$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The sum of $q$ over all test cases is at most $2 \times 10^5$
$s_i \in \{\texttt{B}, \texttt{R}\}$
The given edges form a tree
$1 \le x_i \le n$

t

\left. \begin{array}{l} n \quad q \\ s \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \\ x_1 \\ x_2 \\ \vdots \\ x_q \end{array} \right\} \times t

For each test case, after each query output one integer, the number of good vertices after applying that query.

\left. \begin{array}{l} a_1 \\ a_2 \\ \vdots \\ a_q \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

13F. Monochrome Levels

Constraints

Input

Output

Samples

13F. Monochrome Levels

Constraints

Input

Output

Samples