لديك شجرة يحتوي كل رأس فيها على مصباح يضيء باللون الأحمر أو الأصفر أو الأخضر. أجب عن العديد من الاستعلامات من الأنواع التالية:

• 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$). من المضمون أن هذه الحواف تشكل شجرة.

يحتوي السطر التالي على سلسلة طولها $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