트리

$N$개의 노드로 이루어진 트리가 있다. 각 노드에는 0번부터 $N-1$번까지 번호가 붙어 있고, 0번 노드가 루트이며, 처음에는 나머지 노드가 모두 0번 노드의 자식이다. 모든 에지의 색깔은 처음에 0이다.

트리에 적용할 수 있는 연산은 세 가지다. 이 연산으로 트리의 모양을 바꾸거나 에지에 색칠을 한다.

1. paint(a, b, c): a번 노드와 b번 노드를 잇는 최단 경로를 찾은 뒤, 그 경로 위의 모든 에지를 색깔 c로 칠한다.
2. move(a, b): a번 노드의 부모를 b번 노드로 바꾼다. 단, b번 노드는 a번 노드를 루트로 하는 부트리에 속하지 않는다. 부모를 바꾸기 전 a번 노드의 부모를 p라고 하면, 새로 생긴 에지 (a, b)는 원래 에지 (a, p)의 색깔을 그대로 갖는다.
3. count(a, b): a번 노드와 b번 노드를 잇는 최단 경로를 찾은 뒤, 그 경로 위의 에지에 칠해진 서로 다른 색깔의 개수를 출력한다.

에지에 칠하는 색깔 c는 정수로 나타낸다.

노드가 6개인 초기 트리에 연산을 move(1,3), move(5,3), paint(5,4,8), move(3,4), paint(0,3,7), count(2,5) 순서로 적용한 경우를 보자. 그림 1이 초기 형태이고, 그림 2부터 그림 4까지가 각 연산을 실행한 뒤에 트리의 모양과 에지 색깔이 어떻게 바뀌는지 차례로 보여 준다.

그림 1. 초기 형태

그림 2. 왼쪽은 move(1,3)을 실행한 뒤, 오른쪽은 move(5,3)을 실행한 뒤

그림 3. paint(5,4,8)을 실행한 뒤

그림 4. 왼쪽은 move(3,4)를 실행한 뒤, 오른쪽은 paint(0,3,7)을 실행한 뒤

마지막 연산 count(2,5)의 결과로는 3을 출력한다. 그림 4의 오른쪽에서 보듯이 2번 노드와 5번 노드 사이 최단 경로 위의 에지 색깔이 $\{0, 7, 8\}$로 세 가지이기 때문이다.

연산이 차례로 주어질 때, 각 연산을 효율적으로 실행하는 프로그램을 작성하시오.

첫째 줄에 트리의 노드 개수 $N$ ($1 \le N \le 10^5$)과 연산의 개수 $K$ ($1 \le K \le 3 \times 10^5$)가 주어진다. 이어서 $K$개의 줄에 연산이 한 줄에 하나씩 주어진다. 각 줄의 첫 번째 정수는 연산의 종류를 나타내는 $r$ ($1 \le r \le 3$)이다.

• $r = 1$이면 paint 연산이고, 같은 줄에 세 정수 $a$, $b$ ($0 \le a, b \le N-1$), $c$ ($0 \le c \le 10^9$)가 이어진다. $a$와 $b$는 노드 번호, $c$는 색깔 번호다.
• $r = 2$이면 move 연산이고, 같은 줄에 두 정수 $a$ ($1 \le a \le N-1$), $b$ ($0 \le b \le N-1$)가 이어진다. 둘 다 노드 번호다.
• $r = 3$이면 count 연산이고, 같은 줄에 두 정수 $a$, $b$ ($0 \le a, b \le N-1$)가 이어진다. 둘 다 노드 번호다.

노드가 $N$개인 초기 트리는 0번 노드가 루트이고 나머지 노드의 부모가 모두 0번 노드이며, 모든 에지의 색깔이 0이다.

paint와 count 연산에서 a번 노드와 b번 노드 사이 최단 경로의 길이는 항상 1,000 이하다.

입력으로 주어진 count 연산마다 그 결과 값을 주어진 순서대로 한 줄에 하나씩 출력한다. a와 b가 같으면 경로에 에지가 없으므로 0을 출력한다.