[NOI2021] 轻重边

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定一棵含有 $n$ 个顶点的树，每条边可能是轻边或重边。在所有操作开始前，树上的全部边都是轻边。你需要依次执行以下两类操作：

1. 给定两个不同的顶点 $a,b$。先对 $a$ 到 $b$ 路径上的每个顶点 $x$，把所有与 $x$ 相连的边变为轻边；然后把 $a$ 到 $b$ 路径所包含的全部边变为重边。
2. 给定两个不同的顶点 $a,b$，求当前 $a$ 到 $b$ 路径上的重边数量。

输入格式

第一行包含一个正整数 $T$，表示数据组数。

对于每组数据，第一行包含两个整数 $n,m$，分别表示顶点数和操作数。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树上的一条无向边。

接下来 $m$ 行，每行包含三个整数 $op,a,b$。$op=1$ 表示第一类操作，$op=2$ 表示第二类操作。保证 $a\ne b$。

输出格式

对于每个第二类操作输出一行一个整数，表示询问路径上的重边数量。

样例输入 1

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

1
3
2
1

数据范围

对于所有数据，$1\le T\le3$，$1\le n,m\le10^5$，$1\le u,v,a,b\le n$。