CF1941G Rudolf and Subway
题目描述
建桥对伯纳德没有帮助，他去哪里都迟到。然后鲁道夫决定教他乘坐地铁。
鲁道夫将地铁地图描绘成一个无向连接图，没有自循环，其中顶点代表车站。任何一对顶点之间最多有一条边。
如果可以绕过其他站点，则可以通过一条边直接在相应站点之间移动，则两个顶点通过一条边连接。鲁道夫和伯纳德居住的城市的地铁有颜色符号。这意味着站点之间的任何边缘都具有特定的颜色。特定颜色的边缘共同形成一条地铁线。地铁线不能包含未连接的边，并形成给定地铁图的连接子图。
地铁地图示例如图所示。
鲁道夫声称，如果这条路线通过最少数量的地铁线路，这条路线将是最佳的。
帮助 Bernard 确定给定出发站和目的地站的最小数量。
输入格式
第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) 表示测试用例的数量。
接下来是测试用例的描述。
每个测试用例的第一行包含两个整数 $ n $ and $ m $ ( $ 2 \le n \le 2 \cdot 10^5, 1 \le m \le 2 \cdot 10^5 $ ) 表示地铁站数量和车站之间的直达路线数量 (即图形边缘).
紧随其后的是 $ m $ 行 表示边缘的描述。描述的每一行包含三个整数 $ u $ , $ v $ , and $ 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 $ 的路线可以通过的最小地铁线路数。
## 样例 #1
### 样例输入 #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
### 样例输入 #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 $ 移动到同一个顶点，所以行数为 $ 0 $ 。
在第四个测试用例中，图的所有边都属于一条线，所以答案是 $ 1 $ 。