Дано дерево, в каждой вершине которого есть лампочка, светящаяся красным, жёлтым или зелёным цветом. Ответьте на множество запросов следующих типов:

• 1 v c — изменить цвет лампочки в вершине $v$ на цвет $c$;
• 2 v — по данной вершине $v$, которая гарантированно светится жёлтым, найти кратчайший светофор в дереве, проходящий через $v$, и вывести количество рёбер в нём. Светофором называется простой путь в дереве, один конец которого красный, другой — зелёный, и хотя бы одна из внутренних вершин пути — жёлтая.

Входные данные

Первая строка входных данных содержит целое число $t$ — количество наборов входных данных ($1 \le t \le 2 \cdot 10^5$). Для каждого набора входных данных:

Первая строка содержит два целых числа $n$ и $q$ — количество вершин в дереве и количество запросов ($1 \le n, q \le 2 \cdot 10^5$).

Каждая из следующих $n - 1$ строк содержит пару целых чисел $u_i$ и $v_i$ — концы ребра дерева ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Гарантируется, что эти рёбра образуют дерево.

Следующая строка содержит строку длины $n$, состоящую из букв «R», «Y», «G», где $i$-я буква обозначает начальный цвет лампочки в $i$-й вершине. «R» означает красный свет, «Y» — жёлтый, «G» — зелёный.

Далее следуют описания $q$ запросов, по одному в строке:

• 1 v c — изменить цвет лампочки в вершине $v$ на цвет $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — вывести длину кратчайшего светофора, проходящего через $v$ ($1 \le v \le n$). Гарантируется, что в момент этого запроса лампочка в вершине $v$ светится жёлтым. Гарантируется, что будет хотя бы один запрос такого типа.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2 \cdot 10^5$. Гарантируется, что сумма $q$ по всем наборам входных данных не превосходит $2 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных и для каждого запроса типа 2 v выведите одно число $d$ — количество рёбер на кратчайшем простом пути в дереве, который начинается в красной вершине, проходит через жёлтую вершину $v$ и заканчивается в зелёной вершине. Если таких путей не существует, выведите $-1$.

Примеры

Входные данные 1

1
7 7
1 2
2 3
2 4
4 5
4 6
6 7
RYGYRGY
2 2
1 7 G
2 4
1 1 Y
2 2
1 5 Y
2 4

Выходные данные 1

2
2
3
-1

Входные данные 2

3
3 2
1 2
2 3
YRG
2 1
1 1 Y
4 3
1 2
2 3
2 4
RYGY
2 2
1 1 Y
2 4
5 8
1 2
2 3
3 4
3 5
YRYGY
2 3
1 5 G
2 1
1 2 Y
2 3
1 1 R
2 3
1 4 Y

Выходные данные 2

-1
2
-1
2
-1
-1
3