Each New Year Timofey and his friends cut down a tree of *n* vertices and bring it home. After that they paint all the *n* its vertices, so that the *i*-th vertex gets color *c*<sub class="lower-index">*i*</sub>.

Now it's time for Timofey birthday, and his mother asked him to remove the tree. Timofey removes the tree in the following way: he takes some vertex in hands, while all the other vertices move down so that the tree becomes rooted at the chosen vertex. After that Timofey brings the tree to a trash can.

Timofey doesn't like it when many colors are mixing together. A subtree annoys him if there are vertices of different color in it. Timofey wants to find a vertex which he should take in hands so that there are no subtrees that annoy him. He doesn't consider the whole tree as a subtree since he can't see the color of the root vertex.

A subtree of some vertex is a subgraph containing that vertex and all its descendants.

Your task is to determine if there is a vertex, taking which in hands Timofey wouldn't be annoyed.
The first line contains single integer *n* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>) — the number of vertices in the tree.

Each of the next *n* - 1 lines contains two integers *u* and *v* (1 ≤ *u*, *v* ≤ *n*, *u* ≠ *v*), denoting there is an edge between vertices *u* and *v*. It is guaranteed that the given graph is a tree.

The next line contains *n* integers *c*<sub class="lower-index">1</sub>, *c*<sub class="lower-index">2</sub>, ..., *c*<sub class="lower-index">*n*</sub> (1 ≤ *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>), denoting the colors of the vertices.
none
4
1 2
2 3
3 4
1 2 1 1
YES
2
3
1 2
2 3
1 2 3
YES
2
4
1 2
2 3
3 4
1 2 1 2
NO
3
2 1
2 3
1 2 3
YES
2
4
1 2
2 4
4 3
1 1 3 2
YES
4
2
1 2
1 1
YES
1
10
5 7
4 5
10 2
3 6
1 2
3 4
8 5
4 9
2 3
15 15 15 15 5 15 26 18 15 15
YES
5
8
1 2
1 3
3 5
3 6
1 4
4 7
4 8
1 3 1 1 1 1 1 2
NO
3
2 1
2 3
4 4 4
YES
1
3
1 2
1 3
1 2 2
YES
1
4
1 4
2 4
3 4
1 2 3 1
YES
4
4
1 2
1 3
1 4
1 2 3 4
YES
1
9
1 2
2 3
3 4
4 5
2 7
7 6
2 8
8 9
1 1 2 2 2 3 3 4 4
YES
2
3
2 1
2 3
4 4 5
YES
2
4
1 2
2 3
3 4
1 2 2 1
NO
from sys import stdin, stdout 
from math import *
import itertools

def wr(text):
    stdout.write(str(text))

def war(a):
    stdout.write(' '.join(map(str, a)) + '\n')

def wrl(text):
    stdout.write(str(text) + '\n')

cin = list(stdin)

s = [i for i in cin[0]]
n = len(s)
t = []
for i in range(4*n):
    t.append(set())

def build(v, tl, tr):
    if tl == tr:
        t[v] = {s[tl]}
    else:
        tm = (tl + tr) // 2
        build(2*v, tl, tm)
        build(2*v + 1, tm + 1, tr)
        t[v] = t[2*v].union(t[2*v + 1])

def getres(v, tl, tr, l, r):
    if (l > r):
        return set()
    elif tl == l and tr == r:
        return t[v]
    else:
        tm = (tl + tr) // 2
        return getres(2*v, tl, tm, l, min(tm, r)).union(getres(2*v + 1, tm + 1, tr, max(l, tm + 1), r))

def update(v, tl, tr, ind, pv, nv):
    if pv == nv:
        return

    if tl == tr:
        t[v] = {nv}
    else:
        tm = (tl + tr) // 2
        if ind <= tm:
            update(2*v, tl, tm, ind, pv, nv)
        else:
            update(2*v + 1, tm + 1, tr, ind, pv, nv)
            
        t[v].remove(pv)
        t[v] = t[2*v].union(t[2*v + 1])

build(1, 0, n - 1)
for x in range(int(cin[1])):
    a, b, c = cin[2+x].split()
    a = int(a)
    b = int(b)
    #print(s, set(s))
    if a == 1:
        update(1, 0, n - 1, b-1, s[b-1], c)
        s[b-1] = c
    else:
        print(len(getres(1, 0 , n - 1, b-1, int(c) - 1)))
