가벼운 간선과 무거운 간선

정점이 $n$개인 트리가 주어진다. 트리의 각 간선은 가벼운 간선 또는 무거운 간선이다. 이 트리에 대해 $m$개의 연산을 수행해야 한다. 처음에는 모든 간선이 가벼운 간선이다. 연산은 두 종류이다.

1. 두 정점 $a$와 $b$가 주어진다. $a$와 $b$를 잇는 경로 위의 모든 정점 $x$($a$와 $b$ 자신을 포함한다)에 대해, $x$에 연결된 모든 간선을 가벼운 간선으로 바꾼다. 또한 $a$와 $b$를 잇는 경로 위의 모든 간선을 무거운 간선으로 바꾼다.

2. 두 정점 $a$와 $b$가 주어진다. $a$와 $b$를 잇는 경로에 있는 무거운 간선의 개수를 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정점의 개수 $n$과 연산의 개수 $m$이 주어진다.

다음 $n-1$개의 줄에는 트리의 간선 $u$, $v$가 한 줄에 하나씩 주어진다.

다음 $m$개의 줄에는 연산 $op_i$, $a_i$, $b_i$가 한 줄에 하나씩 주어진다. $op_i = 1$이면 첫 번째 종류의 연산이고, $op_i = 2$이면 두 번째 종류의 연산이다.

모든 연산에서 $a_i \ne b_i$이다.

두 번째 종류의 연산마다 답을 한 줄에 하나씩 출력한다.

모든 테스트 데이터에 대해 $T \le 3$이고, $1 \le n,m \le 10^5$이다.