Þér er gefið tré þar sem hver hnútur hefur ljósaperu sem lýsir rauðu, gulu eða grænu. Svaraðu mörgum fyrirspurnum af eftirfarandi gerðum:

• 1 v c — breyttu lit ljósaperunnar í hnúti $v$ í lit $c$;
• 2 v — gefinn er hnútur $v$, sem tryggt er að lýsi gulu; finndu stysta umferðarljósið í trénu sem fer í gegnum $v$ og prentaðu fjölda leggja í því. Umferðarljós er skilgreint sem einfaldur vegur í trénu þar sem annar endinn er rauður, hinn er grænn og að minnsta kosti einn af innri hnútum vegarins er gulur.

Inntak

Fyrsta línan í inntakinu inniheldur heiltölu $t$, fjölda prófunartilvika ($1 \le t \le 2 \cdot 10^5$). Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur, $n$ og $q$ — fjölda hnúta í trénu og fjölda fyrirspurna ($1 \le n, q \le 2 \cdot 10^5$).

Hver af næstu $n - 1$ línum inniheldur par af heiltölum, $u_i$ og $v_i$ — endapunkta leggs í trénu ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Það er tryggt að þessir leggir myndi tré.

Næsta lína inniheldur streng af lengd $n$ sem samanstendur af bókstöfunum „R“, „Y“, „G“, þar sem $i$-ti stafurinn táknar upphaflegan lit ljósaperunnar í $i$-ta hnútnum. „R“ þýðir rautt ljós, „Y“ — gult, „G“ — grænt.

Þar á eftir fylgja lýsingar á $q$ fyrirspurnum, ein í hverri línu:

• 1 v c — breyttu lit ljósaperunnar í hnúti $v$ í lit $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — prentaðu lengd stysta umferðarljóssins sem fer í gegnum $v$ ($1 \le v \le n$). Það er tryggt að þegar þessi fyrirspurn berst lýsi ljósaperan í hnúti $v$ gulu. Það er tryggt að það verði að minnsta kosti ein fyrirspurn af þessari gerð.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \cdot 10^5$. Það er tryggt að summa $q$ yfir öll prófunartilvik fari ekki yfir $2 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik og fyrir hverja fyrirspurn af gerðinni 2 v skal prenta eina tölu $d$ — fjölda leggja á stysta einfalda veginum í trénu sem byrjar í rauðum hnúti, fer í gegnum gula hnútinn $v$ og endar í grænum hnúti. Ef slíkir vegir eru ekki til skal prenta $-1$.

Dæmi

Inntak 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

Úttak 1

2
2
3
-1

Inntak 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

Úttak 2

-1
2
-1
2
-1
-1
3