Мистер Китаюта только что приобрёл неориентированный граф, состоящий из n вершин и m ребер. Вершины графа пронумерованы от 1 до n. i-е ребро, соединяющее вершины ai и bi, окрашено в цвет ci.
Мистер Китаюта хочет, чтобы вы обработали следующие q запросов.
i-й запрос состоит из двух целых чисел — ui и vi.
Найдите количество цветов, таких, что ребра этого цвета непосредственно или косвенно соединяют вершину ui и вершину vi (т. е. по рёбрам только этого цвета можно добраться от вершины ui до вершины vi).
Выходные данные
Для каждого запроса выведите ответ на отдельной строке.
Примечание
Рассмотрим первый пример.
Рисунок выше иллюстрирует первый пример. - Вершина 1 и вершина 2 соединены цветами 1 и 2.
- Вершина 3 и вершина 4 соединены цветом 3.
- Вершина 1 и вершина 4 не соединены никаким цветом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 2 1
1 2 2
2 3 1
2 3 3
2 4 3
3
1 2
3 4
1 4
|
2
1
0
|
|
2
|
5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4
|
1
1
1
1
2
|