AT_abc040_d [ABC040D] 道路の老朽化対策について

在某个国家有 $N$ 个城市，每个城市编号为 $1$ 到 $N$。这些城市之间有 $M$ 条道路，第 $i$ 条道路连接城市 $a_i$ 和城市 $b_i$，并且是在 $y_i$ 年修建的。 这个国家的国民非常担心安全，因此他们认为太老的道路有较高的事故风险，有时会选择不使用这些道路。现在你需要调查这个国家的交通状况。 给定 $Q$ 位国民的信息。对于第 $j$ 位国民，已知他住在城市 $v_j$，并且不会使用修建年份不晚于 $w_j$ 年（即 $w_j$ 年及以前）的道路。 对于每位国民，求出仅通过道路能够从他所居住的城市到达的城市数量。

输入按以下格式从标准输入读入。 > $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\leq N\leq 100,\!000$ - $0\leq M\leq 200,\!000$ - $1\leq a_i, b_i\leq N$ - $a_i\neq b_i$ - $1\leq y_i\leq 200,\!000$ - $1\leq Q\leq 100,\!000$ - $1\leq v_j\leq N$ - $0\leq w_j\leq 200,\!000$ ## 部分分 - 对于 $50$ 分的测试点，满足 $N\leq 1,\!000$，$M\leq 2,\!000$，$Q\leq 1,\!000$。 ## 样例解释 1 对于每一位国民，答案如下： - 第 1 位国民住在城市 1，不会使用 $2000$ 年及以前修建的道路。城市 1 唯一连接的道路是在 $2000$ 年修建的，因此无法前往其他城市，答案为 $1$。 - 第 2 位国民住在城市 1，可以前往城市 2 和 3。但不会使用 $1999$ 年及以前修建的道路，因此无法前往城市 4，答案为 $3$。 - 第 3 位国民不会使用 $1995$ 年及以前修建的道路，但所有道路都比这更新，因此可以到达所有城市，答案为 $5$。 ## 样例解释 3 请注意，可能存在两座城市之间有两条或以上的道路，也可能存在即使使用所有道路也无法到达的城市。 由 ChatGPT 4.1 翻译