Kitayuta 先生刚刚购买了一个有 n 个顶点和 m 个边的无向图。图的顶点编号为 1 到 n。每条边,即边 i,都有一个颜色 ci,连接顶点 ai 和 bi。
Kitayuta 先生希望您处理以下 q 个查询。
在第 i 个查询中,他给了你两个整数 - 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。
输出
对于每个查询,在单独的行中打印答案。
示例
输入 #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
输出 #1
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
输出 #2
1 1 1 1 2
注意
让我们考虑第一个示例。
上图显示了第一个示例。
- 顶点 1 和顶点 2 通过颜色 1 和 2 连接。
- 顶点 3 和顶点 4 通过颜色 3 连接。
- 顶点 1 和顶点 4 未通过任何单一颜色连接。