D. Цветной граф мистера Китаюта
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мистер Китаюта только что приобрёл неориентированный граф, состоящий из 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 не соединены никаким цветом.