题目描述

给出一个 $n$ 个点，$m$ 条边的无向图，每条边上是有颜色的。有 $q$ 组询问。

对于第 $i$ 组询问，给出点对 $u_i,v_i$， 求有多少种颜色 $c$，满足存在至少一条从 $u_i$ 到 $v_i$ 的路径，使得该路径上的所有边的颜色均为 $c$。

输入格式

第一行两个整数 $n,m$ 分别表示点的个数和边的个数。

接下来 $m$ 行，每行三个整数 $x_i,y_i,c_i$，表示有一条连接点 $x_i,y_i$ 的边，且该边的颜色为 $c_i$。

接下来一行一个整数 $q$，表示询问的个数。

接下来 $q$ 行，每行两个整数 $u_i,v_i$，表示一组询问。

$2 \le n \le 10^5$，$1 \le m,q \le 10^5$，$1\le x_i,y_i,u_i,v_i \le n$，$1 \le c_i \le m$。

输出格式

对于每一组询问，在单独的一行输出对应的答案。

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