問題文
在某些国家/地区 有 N 个城市,每个城市都有 它们的编号最大为 1 从 N 。连接这些城市 M 有一条路,i 真正的道路是城市 a_i 和城市 它连接 b_i , 它建于y_i 。
这个国家的人民是非常焦虑的人,所以他们可能不会使用太旧的道路,因为他们认为发生事故的风险很高。因此您决定调查这个国家的交通状况。
Q 给出了国家信息。j 关于第一个公民、城市 我住在 v_j ,它的建造年份是 w_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
Q 对于每个国家,答案如下。
- 1 第一人称是城市 我住在 1 。 请勿使用2000 之前修建的道路。城市 通向 1 的唯一路径 2000 自当年建成以来,这座城市 除了 1 之外你不能去任何其他地方。因此答案是 我住在 1 。
- 2 第一人称是城市 我住在 1 和城市 2 呀 您可以前往 3 。然而, 由于1999 之前修建的道路未使用,该市 4 。因此答案是 3 。
- 3 第一个人是 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
连接相同两个城市的道路 2 请注意,可能不仅仅是书籍,而且某些城市可能无法通过所有道路到达。