25973번 - 어지러운 트리

호반우가 키우던 애완용 트리가 병에 걸려 어지럼증을 호소하고 있다. 트리는 어지러워서 루트를 계속 바꾸면서 균형을 잡고 있다. 호반우는 트리를 관찰하던 중 신기해서 트리에게 아래 쿼리를 물어봤다. 트리는 어지러운 탓에 쿼리에 제대로 답하지 못했다. 불쌍한 트리를 위해 답을 대신 찾아주자.

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

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

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

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

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

2번 쿼리가 주어질 때 마다 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.

2번 쿼리는 적어도 하나 이상 주어진다.

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