问题描述

某个国家有 $N$ 个城市，分别编号从 $1$ 到 $N$。这些城市之间有 $M$ 条道路，第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$，并且是在第 $y_i$ 年建造的。

因为这个国家的居民非常担心，过于古老的道路存在较高的事故风险，所以有时候不会使用旧道路。因此，你决定对这个国家的交通情况进行调查。

给定 $Q$ 个居民的信息。对于第 $j$ 个居民，已知他居住在城市 $v_j$，并且不会使用建造年份早于或等于 $w_j$ 年的道路。

对于每个居民，请计算他们可以通过道路从所居住的城市到达的城市数量。

约束条件

• $1 ≦ N ≦ 100,000$
• $0 ≦ M ≦ 200,000$
• $1 ≦ a_i,b_i ≦ N$
• $a_i ≠ b_i$
• $1 ≦ y_i ≦ 200,000$
• $1 ≦ Q ≦ 100,000$
• $1 ≦ v_j ≦ N$
• $0 ≦ w_j ≦ 200,000$

部分得分

• 对于 $50$ 分的测试用例，满足 $N ≦ 1,000$，$M ≦ 2,000$，$Q ≦ 1,000$ 的限制。

输入

输入通过标准输入给出，具体格式如下。

$N$ $M$ $a_1$ $b_1$ $y_1$ : $a_M$ $b_M$ $y_M$ $Q$ $v_1$ $w_1$ : $v_Q$ $w_Q$

输出

输出 $Q$ 行。其中第 $j$ 行输出第 $j$ 个居民可以通过道路到达的城市数量。

示例输入1

5 4
1 2 2000
2 3 2004
3 4 1999
4 5 2001
3
1 2000
1 1999
3 1995

示例输出1

1
3
5

对于每个居民，答案如下：

• 第一个居民住在城市 $1$，并且不使用建造年份早于 $2000$ 年的道路。只有一条连接到城市 $1$ 的道路是在 $2000$ 年建造的，所以无法到达除城市 $1$ 外的其他城市。因此答案为 $1$。
• 第二个居民住在城市 $1$，可以到达城市 $2$ 和 $3$，但是不能去城市 $4$，因为他不使用建造年份早于 $1999$ 年的道路。因此答案为 $3$。
• 第三个居民不使用建造年份早于 $1995$ 年的道路，但是所有的道路都是比 $1995$ 年更新的，所以可以通过所有道路到达所有城市。因此答案为 $5$。

示例输入2

4 5
1 2 2005
3 1 2001
3 4 2002
1 4 2004
4 2 2003
5
1 2003
2 2003
1 2001
3 2003
4 2004

示例输出2

3
3
4
1
1

示例输入3

4 5
1 2 10
1 2 1000
2 3 10000
2 3 100000
3 1 200000
4
1 0
2 10000
3 100000
4 0

示例输出3

3
3
2
1

请注意，同一对城市之间可能有多条道路，并且可能存在无法通过任何道路到达的城市。