← 返回题目列表

Codeforces · 506/D

D. 北裕太先生的彩色图表

中文机器翻译题面 查看原题

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 未通过任何单一颜色连接。