ADAAPPLE - Ada and Apple


Ada the Ladybug is currently on a trip on apple tree. There are many apples on the tree connected with branches. Each apple is inhabited by either Psylloideas or by Woolly Apple Aphids. Psylloideas and Aphids doesn't like each other, so it is strictly prohibited to walk from apple of Psylloideas to apple of aphids (and vice versa). Ada has some questions, whether it is possible to go from node I to node J.

Anyway note, that as Aphids and Psyllodeas doesn't like each other, they sometime conquer an apple of the others. Also note, that it is a real apple tree (not some bush) so no apple is connected with more than 50 other apples.

Input

The first line contains 1 ≤ N, Q ≤ 3*105 , number apples on tree and number for queries.

The next line contains N characters (either 0 or 1), indicating whether ith apple belongs to Psyllodeas or to Aphids.

Next N-1 lines contains two numbers, the branches (edges) of apple tree (0 ≤ I, J < N, I ≠ J).

Each of following Q lines contains one of following types of queries:

0 I, 0 ≤ I < N, meaning that ownership of Ith apple has changed.

1 I J, 0 ≤ I, J < N, question, whether it is possible to go from Ith to Jth apple.

Output

For each query of second kind (1) print "YES", if it is possible or "NO" if it is impossible!

Example Input

8 11
00111100
0 1
1 7
1 2
2 3
2 6
2 4
4 5
1 1 2
1 0 7
1 6 5
1 2 3
1 6 7
0 2
1 1 2
1 0 7
1 6 5
1 2 3
1 6 7

Example Output

NO
YES
NO
YES
NO
YES
YES
NO
NO
YES

hide comments
vamsi_0912: 2018-12-17 04:07:19

What is 0 and what is 1. I am not able to get it

Last edit: 2018-12-17 04:07:52
soham_12345: 2018-06-16 22:01:56

Simple HLD :D

sahil_1994: 2018-04-07 14:02:14

can it solved using square root decomposition of tree ?

morass: 2017-02-23 11:16:24

@[Rampage] Blue.Mary: You are right, Thank you! Gotta repair

[Rampage] Blue.Mary: 2017-02-23 11:03:47

The input section should contain "N-1 lines: The description of the tree."


Added by:Morass
Date:2017-02-12
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:BTCODE_G