题目描述

在遥远的未来，地球被外来文明入侵了，在这危机的关头，人类表现出前所未有的团结，为了让更多的人活下来，联合政府决定联合地球上的所有科学家，共同改造那些被联合政府精心挑选出来的人类，使他们变成拥有超能力的超人，然后派他们去消灭这个地球上的外星生物。这个辉煌而伟大的计划，被命名为“拯

救地球”计划。

幸运的是你也被选中并且成功被改造成为了超人，每次任务，联合政府都会派你通过传送门去联合政府指定的一个国家，而你的任务就是：你要尽可能多的消灭从这个国家开始往外拓展的外星生物，从而拯救尽可能多的国家。

地球上有 n 个国家，有 m 条无向道路，每条道路上只有一个外星生物（地球上的外星生物全部都在道路上，国家里面没有外星生物），每个外星生物都有一个防御值，接着你有 q 次任务，每次任务联合政府会让你拥有 w 的攻击力（每

次任务的攻击力是一直不变的），然后用传送门将你送去国家 x（国家 x 已经被你拯救），你的任务就是拯救尽可能多的国家。（如果国家 a 与国家 b 之间有一条道路，国家 a 已经被你拯救，并且你的攻击值大于等于这条道路上外星生物的防御值，那么国家 b 能被你拯救，否则你无法通过这条道路拯救国家 b）

对于每次任务，输出你最多能拯救的国家数目，每次任务独立，互不影响。

输入格式

输入第一行三个正整数 n，m，q，分别表示地球上的国家数，道路数，以及你的任务数。接下来 m 行，每行三个整数 x，y，w，表示国家 x 和国家 y 之间有一条无向道路，并且该道路上只有一个外星怪物，它的防御值为 w，保证防御值为正整数。接下来 q 行，每行两个整数 x，w，表示每次任务你会被派到国家 x，并且让你拥有 w 的攻击力，每次任务独立，互不影响。

输出格式

输出共 q 行，每行一个正整数，表示每次任务你最多能拯救的国家数目。

输入/输出例子1

5 8 5
1 5 4
1 2 1
5 2 2
2 4 3
5 4 4
4 3 3
2 3 2
2 3 3
1 3
2 2
2 4
3 1
4 3

5
4
5
1
5

样例解释

【样例 1 解释】

第一次任务能拯救的国家编号为：1,2,3,4,5

第二次任务能拯救的国家编号为：1,2,3,5

第三次任务能拯救的国家编号为：1,2,3,4,5

第四次任务能拯救的国家编号为：3

第五次任务能拯救的国家编号为：1,2,3,4,5

【数据范围】

对于 20%的数据n ≤10^3,m ≤ 2*10^3,q ≤ 10^3, w≤ 10^9

对于另外20%的数据n≤ 10^5,m ≤ 2*10^5,q ≤10^5,w≤100

对于再另外20%的数据n≤10^5,m ≤2*10^5,q ≤10^5, w≤10^9 保证每次任务的输入的x都一样

对于剩余 40%的数据n≤10^5,m≤2*10^5,q≤10^5,w≤ 10^9

每次任务独立，互不影响表示：

每次任务所拯救的国家在其他任务中还是需要重新被拯救的，每次任务所消灭的外星生物在其他任务中还是会重新存在的。