개미 군집

여러 개미 군집이 사는 개미 둥지를 한 과학자 팀이 분석했다. 둥지는 트리 구조이다. 각 노드는 개미 군집이 사는 실제 장소를 나타내고, 각 간선은 두 군집을 잇는 터널을 나타낸다. 각 군집은 정확히 하나의 색을 가지며, 그 색은 바뀔 수 있다. 색 변화는 주어진 두 군집 $A$와 $B$를 잇는 경로 위에서, 특정 색 $c$를 가진 군집들 가운데 가장 가까운 쌍에 따라 정해진다. 두 군집 사이의 거리는 두 군집을 잇는 경로의 간선 수이다.

예를 들어 그림 A.1 (a)는 1번부터 5번까지 번호가 붙은 다섯 군집의 트리이다. 1번부터 5번 군집까지 색은 순서대로 1, 2, 2, 2, 1이다. 색 2와 2번, 5번 군집에 대해, 경로 위에서 가장 가까운 색 2 군집 쌍은 (2번, 3번)이다. 2번과 4번 군집에 대해서는 (3번, 4번) 쌍이 가장 가깝다.

그림 A.1 (b)처럼 3번 군집의 색이 2에서 3으로 바뀌었다고 하자. 그러면 색 2인 군집이 하나뿐이므로, 2번과 5번 군집 사이 경로에는 색 2의 가장 가까운 쌍이 없다. 2번과 4번 군집에 대해서는 색 2의 가장 가까운 쌍이 (2번, 4번)이 된다.

군집의 색, 트리, 그리고 순서가 정해진 업데이트 명령과 질의 명령이 주어질 때, 각 질의 $(A, B, c)$마다 군집 $A$와 $B$ 사이에서 색 $c$를 가진 가장 가까운 군집 쌍을 찾는 프로그램을 작성하라.

첫 줄에 두 정수 $n$과 $q$가 주어진다 ($2 \le n \le 100{,}000$, $2 \le q \le 100{,}000$). $n$은 군집의 수이고, $q$는 업데이트와 질의 명령의 수이다. 군집은 1번부터 $n$번까지 번호가 붙고, 색은 $\{1, 2, \cdots, n\}$의 정수이다. 다음 줄에는 1번 군집부터 $n$번 군집까지의 색이 순서대로 $n$개 주어진다. 이어서 $n-1$개의 줄에 터널로 연결된 두 군집 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 주어진다. 이어서 $q$개의 줄에 $(S, A, c)$ 또는 $(S, A, B, c)$ 형태의 명령이 주어진다. $S$는 대문자 U 또는 Q이다. U이면 $A$번 군집의 색을 $c$로 바꾼다 ($1 \le A, c \le n$). Q이면 군집 $A$와 $B$ 사이 경로에서 색 $c$를 가진 가장 가까운 쌍의 거리를 출력한다 ($1 \le A, B, c \le n$). 명령은 입력된 순서대로 실행한다.

$S =$ Q인 각 질의 $(S, A, B, c)$에 대해, 현재 색 상태에서 군집 $A$와 $B$ 사이 경로 위의 색 $c$ 군집 쌍 중 가장 가까운 쌍의 거리를 한 줄에 출력한다. 그런 쌍이 없으면 -1을 출력한다.

그림 A.1은 첫 번째 샘플 테스트에 해당하는 개미 둥지를 보여 준다.