10167: SPOJ ADABRANC - Ada and Branches
[Creator : ]
Description
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 Xi weight (so if some creature with more weight 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?
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 test-case 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 weight.
NOTE Multiedges are allowed.
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 weight.
NOTE Multiedges are allowed.
Output
For each query, output the number of fruits Ada can get to.
Sample 1 Input
4 4 3
1 2 4
2 3 3
3 0 4
0 1 3
1 3
1 4
1 5
Sample 1 Output
4
2
1
Sample 2 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
Sample 2 Output
7
1
1
3
8
7
4
8