G. Рудольф и метро
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бернарду не помогло строительство мостов, и он все равно продолжил везде опаздывать. Тогда Рудольф решил научить его оптимально пользоваться метро.

Рудольф изобразил карту метро как неориентированный связный граф, не имеющий петель, в котором вершины представляют собой станции метро. Любая пара вершин соединяется не более чем одним ребром.

Две вершины соединяются ребром, если между соответствующими станциями метро можно переместиться на поезде напрямую, минуя другие станции. Метро в городе, в котором живут Рудольф и Бернард, имеет цветовую нотацию. Это значит, что любое ребро между какими-либо станциями имеет определенный цвет. Ребра определенного цвета в совокупности образуют ветку метро. Ветка метро не может содержать не связанные между собой ребра, то есть образует связный подграф заданного графа метро.

Пример карты метро приведен на рисунке.

Рудольф утверждает, что маршрут будет максимально оптимальным, если он будет проходить через минимальное количество веток.

Помогите Бернарду определить это минимальное количество для заданных станций отправления и назначения.

Входные данные

Первая строка содержит одно целое число $$$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
Входные данные
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
1
2
Примечание

Граф метро для первого примера приведен на рисунке в условии.

В первом наборе тестовых данных из вершины $$$1$$$ в вершину $$$3$$$ можно добраться по пути $$$1 \rightarrow 2 \rightarrow 3$$$, воспользовавшись только зеленой веткой.

Во втором наборе тестовых данных из вершины $$$1$$$ в вершину $$$6$$$ можно добраться по пути $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 6$$$, воспользовавшись зеленой и синей веткой.

В третьем наборе тестовых данных из вершины $$$6$$$ в ту же самую вершину не нужно ехать, поэтому количество веток равно $$$0$$$.

В четвертом наборе тестовых данных все ребра графа принадлежат одной ветке, поэтому ответ $$$1$$$.