Cho một cây có ~N~ đỉnh được đánh số từ ~1~ đến ~N~, mỗi đỉnh được gán một màu nhất định. Thái hôm nay được thầy dạy thêm về cây con là một đồ thị liên thông có đỉnh và cạnh của cây ban đầu. Thái rất hứng thú và quyết định tô lại màu một số đỉnh nhất định và tự thử thách bản thân khi chọn một màu rồi tìm cây con nhỏ nhất chứa tất cả các đỉnh có màu đó. Hay nói rõ hơn, Thái sẽ chọn màu ~X~ và tìm cây con có ít đỉnh nhất mà các đỉnh có màu ~X~ đều thuộc cây con đó.

Thái biết sắp tới có kì thi chọn đội tuyển Tỉnh nên muốn nhờ các bạn giúp đỡ giải bài toán trên.

Yêu cầu: Với truy vấn U x c, Thái sẽ tô màu ~c~ cho đỉnh ~x~. Còn với truy vấn Q c, Thái muốn biết số lượng cạnh trong cây con nhỏ nhất chứa tất cả các đỉnh màu ~c~ ~(1 \le x \le N,\ 1 \le c \le 10^5)~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ là số đỉnh của cây ~(2 \le N \le 10^5)~.

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ thể hiện một cạnh ~(u, v)~ trên cây ~(1 \le u, v \le N)~.

• Dòng tiếp theo chứa ~N~ số nguyên, số thứ ~i~ là màu ~c_i~ của đỉnh ~i~ trên cây ~(1 \le c_i \le 10^5)~.

• Dòng tiếp theo chứa số nguyên ~Q~ là số truy vấn.

• ~Q~ dòng tiếp theo, mỗi dòng có một trong hai dạng sau:

  • Dạng 1: U x c

  • Dạng 2: Q c

Output

Ghi ra file TREE.OUT. Với mỗi truy vấn Q c, ghi ra số lượng cạnh trong cây con cần tìm. Nếu không tồn tại đỉnh nào có màu ~c~ thì ghi ra -1.

Sample Input 1

5
1 2
2 3
3 4
2 5
1 2 1 2 3
6
Q 1
Q 2
Q 3
Q 4
U 5 1
Q 1

Sample Output 1

2
2
0
-1
3

Notes

Giới hạn:

• ~20\%~ số điểm tương ứng với ~20\%~ số test có duy nhất ~1~ truy vấn dạng 2, còn lại là dạng 1;

• ~10\%~ số điểm tương ứng với ~10\%~ số test có số lượng màu ~< 10~;

• ~70\%~ số điểm tương ứng với ~70\%~ số test còn lại không có ràng buộc gì thêm.