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*10^{5} , number apples on tree and number for queries.
The next line contains N characters (either 0 or 1), indicating whether i^{th} apple belongs to Psyllodeas or to Aphids.
Next N1 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 I^{th} apple has changed.
1 I J, 0 ≤ I, J < N, question, whether it is possible to go from I^{th} to J^{th} 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:
20181217 04:07:19
What is 0 and what is 1. I am not able to get it


soham_12345:
20180616 22:01:56
Simple HLD :D 

sahil_1994:
20180407 14:02:14
can it solved using square root decomposition of tree ? 

morass:
20170223 11:16:24
@[Rampage] Blue.Mary: You are right, Thank you! Gotta repair 

[Rampage] Blue.Mary:
20170223 11:03:47
The input section should contain "N1 lines: The description of the tree." 
Added by:  Morass 
Date:  20170212 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  BTCODE_G 