Ald

A tree is given. It has $n$ vertices, labeled from $1$ to $n$.

Denote the path between vertices $a$ and $b$ as $(a, b)$. The $d$-set of a path is the set of all vertices of the tree whose distance from at least one vertex on the path is at most $d$. For example, the $0$-set of a path is the set of its own vertices. The distance between two vertices is the number of edges on the path connecting them.

Let $S$ be a multiset of tree paths. Initially, $S$ is empty. Process the following queries.

• 1 $u$ $v$: add the path $(u, v)$ to $S$ ($1 \le u, v \le n$).
• 2 $u$ $v$: delete one copy of the path $(u, v)$ from $S$ ($1 \le u, v \le n$). $(u, v)$ and $(v, u)$ denote the same path. For example, if $S=\{(2, 3), (2, 3)\}$, then the query 2 3 2 leaves $S=\{(2, 3)\}$. Before this query, it is guaranteed that $S$ contains $(u, v)$ or $(v, u)$.
• 3 $d$: print the size of the intersection of the $d$-sets of all paths in $S$ ($0 \le d \le n$). If $S$ is empty, print $0$.

The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Each test case starts with a line containing the number of vertices $n$ and the number of queries $q$ ($1 \le n, q \le 10^5$). The next $n-1$ lines each contain the endpoints $u_i$ and $v_i$ of the $i$-th edge. The last $q$ lines contain queries in the format described above. The sum of $n$ over all test cases does not exceed $10^5$, and the sum of $q$ over all test cases does not exceed $10^5$.

For each query of type 3, print the answer on its own line.