You are given a tree with $N$ vertices where the $i^\text{th}$ edge connects vertices $u_i$ and $v_i$. Each edge on this tree is either a **light** or a **heavy** edge. Initially, all edges are light.

You should process the following $Q$ operation of $2$ types:

- $\texttt{1 a b}$, for all edges
- if two of the endpoints of the edge are contained in the path from $a$ to $b$, then the edge becomes heavy
- if one of the endpoints of the edge are contained in the path from $a$ to $b$, the edge becomes light

- $\texttt{2 a b}$ count the number of heavy edges on the path from $a$ to $b$

Each test contains multiple test cases. The first line of input contains a single integer $T$, the number of test cases. The description of the test cases follows.

The first line of each test case contains two integer $N$ and $Q$, the size of the tree and the number of operations you need to process.

The following $N-1$ lines of each test case contains two integer $u_i$ and $v_i$, describing the vertices that the $i^\text{th}$ edge connects.

The following $Q$ lines of each test case contains three integers $op_i$, $a_i$ and $b_i$, describing an operation.

For each operation of type $2$, print the answer in a separate line.

- $1 \leq T \leq 3$
- $1 \leq N,Q \leq 10^5$
- $1 \leq u_i,v_i \leq N$
- It is guaranteed that the given edges form a tree.
- $op_i \in {1,2}$
- $1 \leq a_i, b_i \leq N$
- $a_i \neq b_i$

- $N,Q \leq 5~000$ ($10$ points)
- each vertex is directly connected to at most $2$ other vertices and for the second type of operation, $a_i$ and $b_i$ are directly connected by an edge ($10$ points)
- each vertex is directly connected to at most $2$ other vertices ($20$ points)
- for the second type of operation, $a_i$ and $b_i$ are directly connected by an edge ($20$ points)
- $N,Q \leq 20~000$ ($20$ points)
- No additional constraints ($20$ points)

```
1
7 7
1 2
1 3
3 4
3 5
3 6
6 7
1 1 7
2 1 4
2 2 7
1 1 5
2 2 7
1 2 1
2 1 7
```

```
1
3
2
1
```

Subtask | Score |
---|---|

1 | 10 |

2 | 10 |

3 | 20 |

4 | 20 |

5 | 20 |

6 | 20 |

7 | 0 |