נתון לך עץ שבו לכל צומת יש נורה המאירה באדום, צהוב או ירוק. ענה על שאילתות רבות מהסוגים הבאים:

• 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