Әрбір төбесінде қызыл, сары немесе жасыл түспен жанатын шамы бар ағаш берілген. Келесі түрдегі көптеген сұраныстарға жауап беріңіз:

• 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$). Бұл қырлардың ағаш құрайтынына кепілдік беріледі.

Келесі жолда «R», «Y», «G» әріптерінен тұратын ұзындығы $n$ жол берілген, мұндағы $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