CF1941G.Rudolf and Subway

Building bridges did not help Bernard, and he continued to be late everywhere. Then Rudolf decided to teach him how to use the subway.

Rudolf depicted the subway map as an undirected connected graph, without self-loops, where the vertices represent stations. There is at most one edge between any pair of vertices.

Two vertices are connected by an edge if it is possible to travel directly between the corresponding stations, bypassing other stations. The subway in the city where Rudolf and Bernard live has a color notation. This means that any edge between stations has a specific color. Edges of a specific color together form a subway line. A subway line cannot contain unconnected edges and forms a connected subgraph of the given subway graph.

An example of the subway map is shown in the figure.

Rudolf claims that the route will be optimal if it passes through the minimum number of subway lines.

Help Bernard determine this minimum number for the given departure and destination stations.

修建桥梁并未帮助伯纳德，他仍然处处迟到。于是鲁道夫决定教他如何乘坐地铁。

鲁道夫将地铁线路图表示为一个无向连通图（不含自环），其中顶点代表车站，任意两个顶点之间至多存在一条边。

若可在不经过其他车站的情况下直接在对应两站间通行，则这两顶点由一条边相连。鲁道夫和伯纳德所在城市的地铁系统采用颜色标记法：即连接各车站的每条边均具有特定颜色；同一种颜色的所有边共同构成一条地铁线路。一条地铁线路不能包含互不连通的边，且必须构成原地铁图的一个连通子图。

地铁线路图的一个示例如下图所示：

鲁道夫声称：当路线所经过的地铁线路数量最小时，该路线即为最优路线。

请帮助伯纳德计算：对于给定的出发站与到达站，此最小线路数是多少？

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

This is followed by descriptions of the test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5$) — the number of subway stations and the number of direct routes between stations (i.e., graph edges).

This is followed by $m$ lines — the description of the edges. Each line of the description contains three integers $u$, $v$, and $c$ ($1 \le u, v \le n, u \ne v, 1 \le c \le 2 \cdot 10^5$) — the numbers of the vertices between which there is an edge, and the color of this edge. It is guaranteed that edges of the same color form a connected subgraph of the given subway graph. There is at most one edge between a pair of any two vertices.

This is followed by two integers $b$ and $e$ ($1 \le b, e \le n$) — the departure and destination stations.

The sum of all $n$ over all test cases does not exceed $2 \cdot 10^5$. The sum of all $m$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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 \ne 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$。

For each testcase, output a single integer — the minimum number of subway lines through which the route from station $b$ to station $e$ can pass.

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

The subway graph for the first example is shown in the figure in the problem statement.

In the first test case, from vertex $1$ to vertex $3$, you can travel along the path $1 \rightarrow 2 \rightarrow 3$, using only the green line.

In the second test case, from vertex $1$ to vertex $6$, you can travel along the path $1 \rightarrow 2 \rightarrow 3 \rightarrow 6$, using the green and blue lines.

In the third test case, there is no need to travel from vertex $6$ to the same vertex, so the number of lines is $0$.

In the fourth test case, all edges of the graph belong to one line, so the answer is $1$.

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

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

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

在第三个测试用例中，无需从顶点 $6$ 出发前往同一顶点，因此所需线路数为 $0$。

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