ADABRANC  Ada and Branches
Ada the Ladybug lives on a bush. A typical bush consists of some fruits connected with branches. Ada wants to travel between some fruits. Problem is that each edge can stand only some X_{i} weigth (so if some creature with more weigth would like to travel over the edge, it would break and the creature would fall of the bush).
Ada wants to make several travels so she asks you (for each such travel) to how many distinct fruits she can get?
Input
The first line of each testcase will contain three integers 2 ≤ N ≤ 10^{5}, the number of fruits, 1 ≤ M ≤ 2*10^{5}, the number of edges and 1 ≤ Q ≤ 3*10^{5}, the number of queries.
The next M lines will contain three integers 0 ≤ a, b < N (a ≠ b), the fruits which are connected by and edge and 1 ≤ X_{i} ≤ 10^{5}.
The next Q lines will contain two integers 0 ≤ a < N, the fruit Ada starts in and 1 ≤ Y ≤ 10^{5}, her actual weigth.
NOTE Multiedges are allowed.
Output
For each query, output the number of fruits Ada can get to.
Example Input
4 4 3 1 2 4 2 3 3 3 0 4 0 1 3 1 3 1 4 1 5
Example Output
4 2 1
Example Input
8 10 8 1 3 3 1 2 2 3 5 1 3 4 3 2 4 7 5 6 2 4 6 8 4 7 3 7 0 1 6 0 4 1 3 1 4 0 5 6 6 6 1 2 3 0 4 5 2
Example Output
7 1 1 3 8 7 4 8
hide comments
shreyas_07:
20201016 03:38:28
Use path compression as well along with DSU 

abhishak69:
20200325 04:38:52
offline queries + dsu 

nadstratosfer:
20200321 22:11:46
Didn't bother to code this one when I had figured out how to do it many months ago, which is a shame as for the current compilers the top 2 runtimes are unreachable. Cool problem nevertheless, huge input gives a tangible measure of every approach and optimization idea; trying to get my C code to a decent performance made me find a method that even allows PyPy to get AC. Once again good job Morass, thanks. 

clarkfric_200:
20190919 14:30:14
Solved it using DSU 

scolar_fuad:
20190708 19:40:17
How to optimize time limit help please ? 

vatsalsonigara:
20190525 06:39:20
Giving Runtime Error in java. Same solution is getting accepted in C++.


divya_9997:
20181226 19:36:23
I solved this problem using DFT. I am getting time limit error. Is there any other approach to get an optimized solution? 

viskey:
20180614 09:11:54
@prashant_1098


prashant_1098:
20180304 07:19:35
How is it possible for the bug to visit 3 fruits when it starts at 6 with weight 6 
Added by:  Morass 
Date:  20171008 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Tunisian Collegiate Training Contest  Round #01 