Dizzy Tree

Hobanu's pet tree is sick and feels dizzy. The tree keeps changing its root to keep its balance. While watching the tree, Hobanu got curious and asked it the queries below. Because of the dizziness, the tree could not answer them correctly. Let's find the answers for the poor tree.

The input is a tree with $N$ nodes whose root is node $1$. The nodes are numbered from $1$ to $N$. Write a program that answers each of the $Q$ queries below.

• 1 x: Change the root to node $x$.
• 2 x: Print the number of pairs $(a, b)$ with $LCA(a, b) = x$. The pairs $(a, b)$ and $(b, a)$ are treated as the same ordered pair. ($a \neq b$)

The first line contains $N$ and $Q$, separated by a space. $(1 \le N \le 200\,000, 1 \le Q \le 200\,000)$

From the second line to line $N$, each line contains two node numbers $a$ and $b$ connected by an edge, separated by a space. $(1 \le a, b \le N)$

From line $N+1$ to line $N+Q$, the queries described above are given.

For each type 2 query, print the answer on its own line, in the order the queries are given. At least one type 2 query is given.

LCA stands for Lowest Common Ancestor. The LCA of $a$ and $b$ is the deepest node that has both $a$ and $b$ as descendants.