Gegeben ist ein Baum, in dem jeder Knoten eine Glühbirne hat, die rot, gelb oder grün leuchtet. Beantworte viele Anfragen der folgenden Typen:

• 1 v c — ändere die Farbe der Glühbirne am Knoten $v$ in die Farbe $c$;
• 2 v — gegeben ist ein Knoten $v$, der garantiert gelb leuchtet; finde die kürzeste Ampel im Baum, die durch $v$ verläuft, und gib die Anzahl ihrer Kanten aus. Eine Ampel ist definiert als ein einfacher Pfad im Baum, dessen eines Ende rot ist, dessen anderes Ende grün ist und bei dem mindestens einer der inneren Knoten des Pfades gelb ist.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl $t$, die Anzahl der Testfälle ($1 \le t \le 2 \cdot 10^5$). Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen, $n$ und $q$ — die Anzahl der Knoten im Baum und die Anzahl der Anfragen ($1 \le n, q \le 2 \cdot 10^5$).

Jede der nächsten $n - 1$ Zeilen enthält ein Paar ganzer Zahlen, $u_i$ und $v_i$ — die Endpunkte einer Kante des Baumes ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Es wird garantiert, dass diese Kanten einen Baum bilden.

Die folgende Zeile enthält eine Zeichenkette der Länge $n$, die aus den Buchstaben „R“, „Y“, „G“ besteht, wobei der $i$-te Buchstabe die anfängliche Farbe der Glühbirne am $i$-ten Knoten angibt. „R“ bedeutet rotes Licht, „Y“ — gelbes, „G“ — grünes.

Danach folgen die Beschreibungen von $q$ Anfragen, eine pro Zeile:

• 1 v c — ändere die Farbe der Glühbirne am Knoten $v$ in die Farbe $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — gib die Länge der kürzesten Ampel aus, die durch $v$ verläuft ($1 \le v \le n$). Es wird garantiert, dass zum Zeitpunkt dieser Anfrage die Glühbirne am Knoten $v$ gelb leuchtet. Es wird garantiert, dass es mindestens eine Anfrage dieses Typs gibt.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $2 \cdot 10^5$ nicht überschreitet. Es wird garantiert, dass die Summe von $q$ über alle Testfälle hinweg $2 \cdot 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall und für jede Anfrage vom Typ 2 v eine einzige Zahl $d$ aus — die Anzahl der Kanten auf dem kürzesten einfachen Pfad im Baum, der an einem roten Knoten beginnt, durch den gelben Knoten $v$ verläuft und an einem grünen Knoten endet. Falls solche Pfade nicht existieren, gib $-1$ aus.

Beispiele

Eingabe 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

Ausgabe 1

2
2
3
-1

Eingabe 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

Ausgabe 2

-1
2
-1
2
-1
-1
3