#P17999. Traffic Lights

Traffic Lights

Traffic Lights

题目描述

给定一棵树,每个顶点的灯泡为红色、黄色或绿色之一。

一条“交通灯路径”是树上的一条简单路径,两个端点分别为红色和绿色,并且至少有一个内部顶点为黄色。路径长度为其包含的边数;路径上其他顶点的颜色没有额外限制。

处理两类操作:

  • 1 v c:将顶点 vv 的颜色改成 cc。
  • 2 v:保证当前 vv 为黄色,求经过 vv 的最短交通灯路径长度;不存在时输出 −1-1。

输入格式

第一行一个整数 tt,1≤t≤2×1051\le t\le2\times10^5。

每个测试用例先输入 n,qn,q,满足 1≤n,q≤2×1051\le n,q\le2\times10^5。

接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i,表示一条边,满足 1≤ui,vi≤n1\le u_i,v_i\le n、ui≠viu_i\ne v_i。保证这些边构成树。

随后一行长度为 nn 的字符串,第 ii 个字符表示顶点 ii 的初始颜色:R 为红色,Y 为黄色,G 为绿色。

接下来 qq 行描述操作,其中 1≤v≤n1\le v\le n,cc 为 R、Y、G 之一。每组至少有一次第 2 类操作,且该操作的查询顶点当时一定为黄色。

所有测试用例的 nn 之和、qq 之和分别不超过 2×1052\times10^5。

输出格式

按顺序对每次第 2 类操作输出一个整数,表示答案。

样例 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

输出

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

输出

-1
2
-1
2
-1
-1
3