คุณได้รับต้นไม้หนึ่งต้นซึ่งแต่ละจุดยอดมีหลอดไฟที่ส่องแสงสีแดง สีเหลือง หรือสีเขียว จงตอบคำถามจำนวนมากในรูปแบบต่อไปนี้:

• 1 v c — เปลี่ยนสีของหลอดไฟที่จุดยอด $v$ เป็นสี $c$
• 2 v — กำหนดจุดยอด $v$ ซึ่งรับประกันว่ากำลังส่องแสงสีเหลือง จงหา สัญญาณไฟจราจร ที่สั้นที่สุดในต้นไม้ที่ผ่านจุดยอด $v$ และแสดงจำนวนเส้นเชื่อมในนั้น สัญญาณไฟจราจรนิยามว่าเป็นวิถีเชิงเดียว (simple path) ในต้นไม้ ซึ่งปลายด้านหนึ่งเป็นสีแดง ปลายอีกด้านหนึ่งเป็นสีเขียว และมีจุดยอดภายในของวิถีอย่างน้อยหนึ่งจุดเป็นสีเหลือง

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $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