搭建桥梁并没有帮助伯纳德,他仍然到处迟到。然后鲁道夫决定教他如何使用地铁。
鲁道夫将地铁地图描述为无向连通图,没有自环,其中顶点代表车站。任意一对顶点之间至多有一条边。
如果可以绕过其他站而直接在相应的站之间移动,则两个顶点通过边连接。鲁道夫和伯纳德居住的城市的地铁有颜色符号。这意味着站点之间的任何边缘都有特定的颜色。特定颜色的边缘一起形成一条地铁线。地铁线路不能包含不连通的边,并且形成给定地铁图的连通子图。
图中显示了地铁地图的示例。
鲁道夫声称,如果经过最少数量的地铁线路,该路线将是最佳路线。
帮助伯纳德确定给定出发站和目的地站的最小数量。
输入
第一行包含一个整数 $$$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$$$。