当前没有测试数据。

以下题面由 AI 翻译。

题目描述

建造桥梁并没有帮助到Bernard，他仍然到处迟到。于是Rudolf决定教他如何乘坐地铁。

Rudolf将地铁地图描绘成一个无向连通图，没有自环，顶点表示车站。任意两个顶点之间最多有一条边。

如果两个顶点对应的车站之间可以直接通行（无需经过其他车站），则它们之间有一条边。Rudolf和Bernard所在城市的地铁采用颜色标记。这意味着每条边都有一个特定的颜色。同一颜色的所有边构成一条地铁线。地铁线不能包含不连通的边，并且必须构成给定地铁图的一个连通子图。

地铁图的一个例子如附图所示。

Rudolf认为，最优路线是经过最少地铁线的路线。

请帮助Bernard确定从起点到终点车站需要经过的最少地铁线数量。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

接下来是各个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$）——分别表示地铁站的数量和直接路线（边）的数量。

接下来 $m$ 行描述边的信息。每行包含三个整数 $u$、$v$ 和 $c$（$1 \le u, v \le n, u \neq v, 1 \le c \le 2 \cdot 10^5$）——表示顶点 $u$ 和 $v$ 之间有一条颜色为 $c$ 的边。保证同一颜色的边构成连通子图。任意两顶点之间最多有一条边。

最后一行包含两个整数 $b$ 和 $e$（$1 \le b, e \le n$）——起点和终点车站。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，$m$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数——从 $b$ 到 $e$ 的路线需要经过的最少地铁线数量。

样例数据

样例输入1

5
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 3
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
1 6
6 6
1 2 1
2 3 1
5 2 2
2 4 2
4 6 2
3 6 3
6 6
4 3
1 2 1
1 3 1
4 1 1
2 3
6 7
1 2 43
1 3 34
4 6 43
6 3 43
2 3 43
5 3 43
4 5 43
1 6

样例输出1

1
2
0
1
1

样例输入2

3
7 9
2 4 1
3 6 1
2 3 5
1 7 1
4 7 1
2 5 4
5 4 4
3 4 1
3 7 1
5 3
6 5
6 5 83691
4 1 83691
5 4 83691
3 2 83691
4 3 83691
5 1
6 7
6 1 83691
6 2 83691
2 5 83691
5 6 83691
2 3 83691
5 4 83574
3 5 83691
1 4

样例输出2

2
1
2

提示

第一个样例中的地铁图如题目描述中的附图所示。

在第一个测试用例中，从顶点 $1$ 到顶点 $3$ 可以走路径 $1 \rightarrow 2 \rightarrow 3$，仅使用绿色线路。

在第二个测试用例中，从顶点 $1$ 到顶点 $6$ 可以走路径 $1 \rightarrow 2 \rightarrow 3 \rightarrow 6$，使用绿色和蓝色线路。

在第三个测试用例中，起点和终点相同（顶点 $6$），因此无需经过任何线路。

在第四个测试用例中，所有边属于同一线路，因此答案为 $1$。