The City of Technomania has created a maze game for the residents of the city. The maze is in the form of a tree. The residents of the city consider even numbers lucky for them as the name of the city has an even number of duplicates $$n$$ and $$a$.$ In the maze, there are N number of posts with each having either a green flag or a red flag $.$ Green flag $($G$)$ means you can move ahead in the maze and Red flag $($R$)$ means you cannot. There is a pavement between the two posts. There are a total of N$-1$ pavements between the N posts.

Jess is a curious child and wants to play the maze game. However, she has an interesting take on the game. She wants to know the maximum number of posts she can reach from each post with the condition that she is allowed to change the even number of red flags. It means she is allowed to change $2,4,6,.....$etc. number of red flags but not allowed to change $1,3,5,.....$etc. number of red flags.

Example:

There are $5$ posts in the maze, N $=5$

There is one red flag $($POST $3)$ and four green flags $($POST $1,$ POST $2,$ POST $4$ and POST $5).$ The initial map of the maze is as below:

POST $1$: If Jess starts her journey from post $1$ which is a green flag, she can cover $3$ posts at max. The path taken is given below:

Note: Jess cannot convert the red flag of Post $3$ to green as she only wants to convert the even number of red flags.

POST $2$: Jess can cover the $3$ posts: POST $1,$ POST $2$ and POST $4.$

POST $3$: Post $3$ is a red flag and since there is no other red flag in the whole maze, Jess will not be able to convert this red flag into the green flag. As a result, she will not be able to cover any post and since post $3$ is also red, it will also not be considered.

POST $4$: Jess can cover the $3$ posts: POST $1,$ POST $2$ and POST $4.$

POST $5$: Post $5$ is a green flag but Jess cannot reach any other post from here as she has a pavement to Post $3$ which is a red flag and cannot be converted to the green flag. The post covered by Jess is $1.$

Jess is not good with counting and wants you to help her with the calculations. Help Jess find the maximum number of posts she can reach with the given conditions.

Input Format

The first line of input consists of an integer, N$,$ representing the number of posts in the maze.

Next N$-1$ lines each consists of two space$-$separated integers, x and y$,$ representing a pavement between the two posts.

The next line of input consists of a string of length N$,$ where the ith character represents the flag $($G or R$)$ at the ith post.

Character G represents the Green Flag and character R represents the Red Flag.

Constraints

$1<=$ N $<=4000$

$1<=$ x$,$ y $<=$N

Output Format

Print the maximum number of posts Jess can reach from each of the posts in separate lines. The line number represents the post number in the output.

Sample TestCase $1$

Input

$5$

$13$

$12$

$24$

$35$

GGRGG

Output

$3$

$3$

$0$

$3$

$1$

Explanation

As explained in the example.

Sample TestCase $2$

Input

$5$

$12$

$13$

$24$

$35$

RGRGR

Output

$4$

$4$

$4$

$4$

$2$

Explanation

The initial map of the maze is given below:

POST $1$: POST $1$ and POST $3$ red flags can be converted to the green flags. Jess can cover $4$ posts: POST $1,$ POST $2,$ POST $3$ and POST $4.$

POST $2$: Jess can cover posts: POST $1,$ POST $2,$ POST $3$ and POST $4.$ A similar pavement as from Post $1$ is followed.

POST $3$: Jess can cover posts: POST $1,$ POST $2,$ POST $3$ and POST $4.$ A similar pavement as from Post $1$ is followed.

POST $4$: Jess can cover posts: POST $1,$ POST $2,$ POST $3$ and POST $4.$ A similar pavement as from Post $1$ is followed.

POST $5$: Jess can cover two posts: POST $5$ and POST $3$ after converting red flags to green flags. She cannot move further as the Post $1$ has a red flag and she can convert only an even number of red flags.

Test Cases Result

Input Result Time $($Sec$)$ Memory Score

Sample Test Case $1$

Passed

$0\mathrm{.}28729\mathrm{.}4180$ View

Sample Test Case $2$

Failed

$0\mathrm{.}29899\mathrm{.}19530$ Hide

Test Case Input

$5$

$12$

$13$

$24$

$35$

RGRGR

Test Case Output

$2$

$2$

$5$

$2$

$2$

Expected Output

$4$

$4$

$4$

$4$

$2$