z-red
Mr. Little Z got tree with N nodes numbered from 1 to N. Each node has a color, red or green. Little Z is sometimes interested in what is the k-th red node on the path from node 1 to node v. He wants you to simulate tree through Q operations of type 1 or 2:
1 k v - print index of the k-th red node on the path from node 1 to node v ( including nodes 1 and v ), ( 1 <= k <= N ), ( 1 <= v <= N )
2 v - change the color of node v, from red to green and from green to red, ( 1 <= v <= N )
InputIn the first line of the standard input there are 2 space separated integers N ( 2 <= N <= 50000 ) and Q ( 1 <= Q <= 150000 ). In the next line there are N characters, i-th characters represents color of node i in the beginning, 0 is for red and 1 is for green color.
Each line of the following N-1 lines contains 2 space separated integers u, v. They denote there is an edge between node u and node v, u and v are different. There is exactly one path between every two nodes in the tree.
Each line of the following N-1 lines contains 2 space separated integers u, v. They denote there is an edge between node u and node v, u and v are different. There is exactly one path between every two nodes in the tree.
OutputOn the standard output for each operation of type 1 print the index of k-th red node or if it doesn't exist print "-1" ( without quotes ).
Input:
Output:
5 3
10101
1 2
1 3
1 5
2 4
1 2 4
2 4
1 2 4Output:
4
-1
Input:
Output:
8 7
00000000
1 2
8 1
2 3
4 2
7 3
5 3
8 6
1 3 5
2 3
1 3 5
1 3 6
2 1
1 3 4
1 2 4Output:
3
5
6
-1
4Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.