← 返回题目列表

Codeforces · 1941/G

G. 鲁道夫和赛百味

中文机器翻译题面 查看原题

搭建桥梁并没有帮助伯纳德,他仍然到处迟到。然后鲁道夫决定教他如何使用地铁。

鲁道夫将地铁地图描述为无向连通图,没有自环,其中顶点代表车站。任意一对顶点之间至多有一条边。

如果可以绕过其他站​​而直接在相应的站之间移动,则两个顶点通过边连接。鲁道夫和伯纳德居住的城市的地铁有颜色符号。这意味着站点之间的任何边缘都有特定的颜色。特定颜色的边缘一起形成一条地铁线。地铁线路不能包含不连通的边,并且形成给定地铁图的连通子图。

图中显示了地铁地图的示例。

鲁道夫声称,如果经过最少数量的地铁线路,该路线将是最佳路线。

帮助伯纳德确定给定出发站和目的地站的最小数量。

输入

第一行包含一个整数 $$$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$$$ 的路线可以经过的最少地铁线路数。

示例

输入 #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$$$ 到同一个顶点,因此行数为 $$$0$$$。

在第四个测试用例中,图的所有边都属于一条线,所以答案是 $$$1$$$。