각 정점에 빨간색, 노란색 또는 초록색으로 빛나는 전구가 있는 트리가 주어집니다. 다음 유형의 질의들에 답하세요:

• 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 유형의 각 질의마다, 빨간색 정점에서 시작하여 노란색 정점 $v$를 지나 초록색 정점에서 끝나는 트리상의 가장 짧은 단순 경로에 있는 간선의 개수를 나타내는 하나의 수 $d$를 출력합니다. 그러한 경로가 존재하지 않으면 $-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