311151: CF1941G. Rudolf and Subway

G. Rudolf and Subwaytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExamplesInput

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

Output

1
2
0
1
1

Input

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

Output

2
1
2

Note

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$.

**题目大意：**

鲁道夫决定教伯纳德如何使用地铁。地铁地图被表示为一个无向连通图，没有自环，顶点代表车站。任意两个顶点之间最多有一条边。如果可以直接在两个车站之间旅行而不经过其他车站，则这两个顶点由一条边连接。这个城市的地铁有一个颜色标记，这意味着车站之间的每条边都有特定的颜色。具有特定颜色的边一起构成一条地铁线。地铁线不能包含未连接的边，并形成一个给定的地铁图的连通子图。

鲁道夫声称，如果路线经过的地铁线最少，则该路线将是最佳的。任务是帮助伯纳德确定从给定出发站到目的站可以经过的最少地铁线数量。

**输入数据格式：**

第一行包含一个整数 $ 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 $）——顶点之间有边的顶点编号和这条边的颜色。保证同颜色的边形成给定地铁图的连通子图。任意两个顶点之间最多有一条边。

接下来是两个整数 $ b $ 和 $ e $（$ 1 \le b, e \ \le n $）——出发站和目的站。

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

**输出数据格式：**

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

**示例输入输出：**

**输入：**
```
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
2
0
1
1
```

**注意：**

- 在第一个测试用例中，从顶点 1 到顶点 3，你可以沿着路径 $ 1 \rightarrow 2 \rightarrow 3 $，只使用绿色线。
- 在第二个测试用例中，从顶点 1 到顶点 6，你可以沿着路径 $ 1 \rightarrow 2 \rightarrow 3 \rightarrow 6 $，使用绿色和蓝色线。
- 在第三个测试用例中，不需要从顶点 6 到同一个顶点，所以地铁线的数量是 0。
- 在第四个测试用例中，图的所有边属于一条线，所以答案是 1。**题目大意：** 鲁道夫决定教伯纳德如何使用地铁。地铁地图被表示为一个无向连通图，没有自环，顶点代表车站。任意两个顶点之间最多有一条边。如果可以直接在两个车站之间旅行而不经过其他车站，则这两个顶点由一条边连接。这个城市的地铁有一个颜色标记，这意味着车站之间的每条边都有特定的颜色。具有特定颜色的边一起构成一条地铁线。地铁线不能包含未连接的边，并形成一个给定的地铁图的连通子图。 鲁道夫声称，如果路线经过的地铁线最少，则该路线将是最佳的。任务是帮助伯纳德确定从给定出发站到目的站可以经过的最少地铁线数量。 **输入数据格式：** 第一行包含一个整数 $ 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 $）——顶点之间有边的顶点编号和这条边的颜色。保证同颜色的边形成给定地铁图的连通子图。任意两个顶点之间最多有一条边。 接下来是两个整数 $ b $ 和 $ e $（$ 1 \le b, e \ \le n $）——出发站和目的站。 所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。所有测试用例的 $ m $ 之和不超过 $ 2 \cdot 10^5 $。 **输出数据格式：** 对于每个测试用例，输出一个整数——从车站 $ b $ 到车站 $ e $ 可以经过的最少地铁线数量。 **示例输入输出：** **输入：** ``` 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 2 0 1 1 ``` **注意：** - 在第一个测试用例中，从顶点 1 到顶点 3，你可以沿着路径 $ 1 \rightarrow 2 \rightarrow 3 $，只使用绿色线。 - 在第二个测试用例中，从顶点 1 到顶点 6，你可以沿着路径 $ 1 \rightarrow 2 \rightarrow 3 \rightarrow 6 $，使用绿色和蓝色线。 - 在第三个测试用例中，不需要从顶点 6 到同一个顶点，所以地铁线的数量是 0。 - 在第四个测试用例中，图的所有边属于一条线，所以答案是 1。