Бернарду не помогло строительство мостов, и он все равно продолжил везде опаздывать. Тогда Рудольф решил научить его оптимально пользоваться метро.
Рудольф изобразил карту метро как неориентированный связный граф, не имеющий петель, в котором вершины представляют собой станции метро. Любая пара вершин соединяется не более чем одним ребром.
Две вершины соединяются ребром, если между соответствующими станциями метро можно переместиться на поезде напрямую, минуя другие станции. Метро в городе, в котором живут Рудольф и Бернард, имеет цветовую нотацию. Это значит, что любое ребро между какими-либо станциями имеет определенный цвет. Ребра определенного цвета в совокупности образуют ветку метро. Ветка метро не может содержать не связанные между собой ребра, то есть образует связный подграф заданного графа метро.
Пример карты метро приведен на рисунке.
Рудольф утверждает, что маршрут будет максимально оптимальным, если он будет проходить через минимальное количество веток.
Помогите Бернарду определить это минимальное количество для заданных станций отправления и назначения.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальное количество веток, через которое может пройти маршрут от станции \(b\) до станции \(e\).
Примечание
Граф метро для первого примера приведен на рисунке в условии.
В первом наборе тестовых данных из вершины \(1\) в вершину \(3\) можно добраться по пути \(1 \rightarrow 2 \rightarrow 3\), воспользовавшись только зеленой веткой.
Во втором наборе тестовых данных из вершины \(1\) в вершину \(6\) можно добраться по пути \(1 \rightarrow 2 \rightarrow 3 \rightarrow 6\), воспользовавшись зеленой и синей веткой.
В третьем наборе тестовых данных из вершины \(6\) в ту же самую вершину не нужно ехать, поэтому количество веток равно \(0\).
В четвертом наборе тестовых данных все ребра графа принадлежат одной ветке, поэтому ответ \(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
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
1
2
|