Problem Description

If faith has a color, it must be miserable red.

A tree is an undirected connected graph without cycles.

You are given a tree of $n$ nodes numbered from $1$ to $n$ The root of the tree is a node number $1$.

The color of $i$-th node is $i$.

For each node $u$ and node $v$ which are connected by an edge, the weight of edge is $1$ if the color of node $u$ is different from the color of node $v$ otherwise the weight of edge is $0$.

Let's denote path between node $u$ and node $v$ as $(u,v)$.

Let's denote the number of edges in $(u,v)$ as $d(u,v)$.

Let's denote the sum of weighted edges in $(u,v)$ as $dist(u,v)$.

if $u$ is an ancestor of $v$ and $v$ is an ancestor of $w$ then $u$ is an ancestor of $w$.

$v\in subtree(u)$ if $u$ is an ancestor of $v$.

Let's denote $max_{i=1}^n d(i,u)$ as $FakeDeep_u$, while $dist(i,u)=0$ and $i$ is an ancestor of $u$.

There are $m$ queries. Each query has one of four types:

$1$ $u$ $c$: change the color of nodes in $(u,1)$ to $c$, $c$ is different from any other color in the tree.

$2$ $u$ $v$: print $dist(u,v)$.

$3$ $u$: print $\sum_{i=1}^n dist(i,u),i\in subtree(u)$.

$4$ : print $\sum_{i=1}^n FakeDeep_i$.

Input

The first line contains an integer $T$ $( 1\leq T\leq 10)$ representing the number of test cases.

For each test case, there are two integer $n$ $(1\leq n,m\leq 10^5)$ representing the number of nodes in the tree and the number of queries.

For next $n-1$ lines, each line contain two numbers $u,v$, which means that there is an edge between $u$ and $v$.

Each of the next $m$ lines contains $1$ or $2$ or $3$ integers:

$1$ $u$ $c$ $(1\leq u\leq n,1\leq c \leq 10^6)$

$2$ $u$ $v$ $(1\leq u,v\leq n)$

$3$ $u$ $(1\leq u\leq n)$

$4$

Output

For each query of type $2,3,4$, output the only line containing just one integer denoting the answer.

1
7 7
1 2
1 6
6 7
3 4
1 3
3 5
1 4 8
1 7 4
4
2 5 7
3 3
1 2 3
4

4
2
1
3