Anda diberikan sebuah pohon yang setiap simpulnya memiliki bola lampu yang bersinar merah, kuning, atau hijau. Jawablah banyak kueri dengan tipe-tipe berikut:

• 1 v c — ubah warna bola lampu pada simpul $v$ menjadi warna $c$;
• 2 v — diberikan simpul $v$, yang dijamin bersinar kuning, carilah lampu lalu lintas terpendek di pohon yang melewati $v$, dan keluarkan banyaknya sisi di dalamnya. Sebuah lampu lalu lintas didefinisikan sebagai sebuah lintasan sederhana pada pohon yang salah satu ujungnya berwarna merah, ujung lainnya berwarna hijau, dan setidaknya satu dari simpul internal lintasan tersebut berwarna kuning.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $t$, banyaknya kasus uji ($1 \le t \le 2 \cdot 10^5$). Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat, $n$ dan $q$ — banyaknya simpul pada pohon dan banyaknya kueri ($1 \le n, q \le 2 \cdot 10^5$).

Masing-masing dari $n - 1$ baris berikutnya berisi sepasang bilangan bulat, $u_i$ dan $v_i$ — ujung-ujung dari sebuah sisi pohon ($1 \le u_i, v_i \le n$; $u_i \ne v_i$). Dijamin bahwa sisi-sisi ini membentuk sebuah pohon.

Baris berikutnya berisi sebuah string dengan panjang $n$ yang terdiri dari huruf-huruf "R", "Y", "G", dengan huruf ke-$i$ menyatakan warna awal bola lampu pada simpul ke-$i$. "R" berarti lampu merah, "Y" — kuning, "G" — hijau.

Kemudian diikuti deskripsi dari $q$ kueri, satu per baris:

• 1 v c — ubah warna bola lampu pada simpul $v$ menjadi warna $c$ ($1 \le v \le n$; $c \in \{\texttt{R}, \texttt{Y}, \texttt{G}\}$);
• 2 v — keluarkan panjang lampu lalu lintas terpendek yang melewati $v$ ($1 \le v \le n$). Dijamin bahwa pada saat kueri ini, bola lampu pada simpul $v$ bersinar kuning. Dijamin bahwa akan ada setidaknya satu kueri dengan tipe ini.

Dijamin bahwa jumlah dari $n$ di seluruh kasus uji tidak melebihi $2 \cdot 10^5$. Dijamin bahwa jumlah dari $q$ di seluruh kasus uji tidak melebihi $2 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji dan untuk setiap kueri bertipe 2 v, keluarkan satu bilangan $d$ — banyaknya sisi pada lintasan sederhana terpendek di pohon yang dimulai dari simpul merah, melewati simpul kuning $v$, dan berakhir di simpul hijau. Jika lintasan seperti itu tidak ada, keluarkan $-1$.

Contoh

Masukan 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

Keluaran 1

2
2
3
-1

Masukan 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

Keluaran 2

-1
2
-1
2
-1
-1
3