#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/13/problems/F

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Monochrome Levels - Repovive Premier Round 5 | Repovive | 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

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

13F. Monochrome Levels

Constraints

Input

Output

Samples

13F. Monochrome Levels

Constraints

Input

Output

Samples