Дано дерево, у кожній вершині якого є лампочка, що світиться червоним, жовтим або зеленим кольором. Дайте відповідь на багато запитів таких типів:

• 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