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
meocondp:
20190221 06:17:18
Last edit: 20190301 16:30:10 

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 