Dane jest drzewo, w którym każdy wierzchołek ma żarówkę świecącą na czerwono, żółto lub zielono. Odpowiedz na wiele zapytań następujących typów:

• 1 v c — zmień kolor żarówki w wierzchołku $v$ na kolor $c$;
• 2 v — mając dany wierzchołek $v$, który z gwarancją świeci na żółto, znajdź najkrótszą sygnalizację świetlną w drzewie przechodzącą przez $v$ i wypisz liczbę krawędzi w niej zawartych. Sygnalizacja świetlna jest zdefiniowana jako ścieżka prosta w drzewie, której jeden koniec jest czerwony, drugi zielony, a co najmniej jeden z wewnętrznych wierzchołków ścieżki jest żółty.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą $t$, liczbę przypadków testowych ($1 \le t \le 2 \cdot 10^5$). Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite, $n$ oraz $q$ — liczbę wierzchołków w drzewie oraz liczbę zapytań ($1 \le n, q \le 2 \cdot 10^5$).

Każdy z kolejnych $n - 1$ wierszy zawiera parę liczb całkowitych, $u_i$ oraz $v_i$ — końce krawędzi drzewa ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Gwarantowane jest, że krawędzie te tworzą drzewo.

Kolejny wiersz zawiera napis o długości $n$ składający się z liter „R”, „Y”, „G”, gdzie $i$-ta litera oznacza początkowy kolor żarówki w $i$-tym wierzchołku. „R” oznacza światło czerwone, „Y” — żółte, „G” — zielone.

Następnie podane są opisy $q$ zapytań, po jednym w wierszu:

• 1 v c — zmień kolor żarówki w wierzchołku $v$ na kolor $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — wypisz długość najkrótszej sygnalizacji świetlnej przechodzącej przez $v$ ($1 \le v \le n$). Gwarantowane jest, że w momencie tego zapytania żarówka w wierzchołku $v$ świeci na żółto. Gwarantowane jest, że pojawi się co najmniej jedno zapytanie tego typu.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$. Gwarantowane jest, że suma $q$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego i dla każdego zapytania typu 2 v wypisz jedną liczbę $d$ — liczbę krawędzi na najkrótszej ścieżce prostej w drzewie, która zaczyna się w czerwonym wierzchołku, przechodzi przez żółty wierzchołek $v$ i kończy się w zielonym wierzchołku. Jeśli takie ścieżki nie istnieją, wypisz $-1$.

Przykłady

Wejście 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

Wyjście 1

2
2
3
-1

Wejście 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

Wyjście 2

-1
2
-1
2
-1
-1
3