| Codeforces Round 286 (Div. 1) |
|---|
| Закончено |
Мистер Китаюта только что приобрёл неориентированный граф, состоящий из n вершин и m ребер. Вершины графа пронумерованы от 1 до n. i-е ребро, соединяющее вершины ai и bi, окрашено в цвет ci.
Мистер Китаюта хочет, чтобы вы обработали следующие q запросов.
i-й запрос состоит из двух целых чисел — ui и vi.
Найдите количество цветов, таких, что ребра этого цвета непосредственно или косвенно соединяют вершину ui и вершину vi (т. е. по рёбрам только этого цвета можно добраться от вершины ui до вершины vi).
В первой строке следуют два целых числа через пробел — n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105), обозначающих количество вершин и количество ребер, соответственно.
В следующих m строках следуют три целых числа через пробел — ai, bi (1 ≤ ai < bi ≤ n) и ci (1 ≤ ci ≤ m). Обратите внимание, что между двумя вершинами может быть несколько ребер. Однако между двумя вершинами не может быть нескольких ребер одного цвета, то есть, если i ≠ j, то (ai, bi, ci) ≠ (aj, bj, cj).
В следующей строке записано целое число — q (1 ≤ q ≤ 105), обозначающее количество запросов.
Затем следуют q строк, содержащих по два целых числа через пробел — ui и vi (1 ≤ ui, vi ≤ n). Гарантируется, что ui ≠ vi.
Для каждого запроса выведите ответ на отдельной строке.
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
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
Рассмотрим первый пример.
Рисунок выше иллюстрирует первый пример. - Вершина 1 и вершина 2 соединены цветами 1 и 2.
- Вершина 3 и вершина 4 соединены цветом 3.
- Вершина 1 и вершина 4 не соединены никаким цветом.
