어지러운 트리

호반우가 키우던 애완용 트리가 병에 걸려 어지럼증을 앓고 있다. 트리는 어지러운 탓에 루트를 계속 바꿔 가며 균형을 잡는다. 호반우는 신기한 나머지 트리에게 아래 쿼리를 물어봤지만, 트리는 어지러워서 제대로 답하지 못했다. 이 트리를 위해 답을 대신 구해 주자.

입력으로 루트가 1번 노드인 노드 $N$개짜리 트리가 주어진다. 트리의 노드는 1번부터 $N$번까지 번호가 붙어 있다. 아래 쿼리가 $Q$번 주어질 때, 각 쿼리를 해결하는 프로그램을 작성하라.

• 1 x: 루트 노드를 $x$번 노드로 바꾼다.
• 2 x: $LCA(a, b) = x$번 노드인 $(a, b)$ 쌍의 가능한 경우의 수를 출력한다. $(a, b)$와 $(b, a)$는 같은 순서쌍으로 본다. ($a \neq b$)

첫 번째 줄에 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 200\,000, 1 \le Q \le 200\,000)$

두 번째 줄부터 $N$번째 줄까지는 간선으로 연결된 두 노드의 번호 $a$, $b$가 공백으로 구분되어 주어진다. $(1 \le a, b \le N)$

$N+1$번째 줄부터 $N+Q$번째 줄까지 위에서 설명한 쿼리가 주어진다.

2번 쿼리가 주어질 때마다 그 답을 한 줄에 하나씩, 주어진 순서대로 출력한다. 2번 쿼리는 하나 이상 주어진다.

LCA는 트리의 최소 공통 조상(Lowest Common Ancestor)이다. $a$와 $b$의 LCA는 $a$와 $b$를 모두 자손으로 가지면서 깊이가 가장 깊은 노드이다.