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 Xi 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 test-case will contain three integers 2 ≤ N ≤ 105, the number of fruits, 1 ≤ M ≤ 2*105, the number of edges and 1 ≤ Q ≤ 3*105, 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 ≤ Xi ≤ 105.

The next Q lines will contain two integers 0 ≤ a < N, the fruit Ada starts in and 1 ≤ Y ≤ 105, 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
clarkfric_200: 2019-09-19 14:30:14

Solved it using DSU

scolar_fuad: 2019-07-08 19:40:17

How to optimize time limit help please ?

vatsalsonigara: 2019-05-25 06:39:20

Giving Runtime Error in java. Same solution is getting accepted in C++.
Please help.

meocondp: 2019-02-21 06:17:18

Last edit: 2019-03-01 16:30:10
divya_9997: 2018-12-26 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: 2018-06-14 09:11:54

@prashant_1098
6 -> 4 (x = 8)
4 -> 2 (x = 7)
So, the bug can visit 3 fruits.

prashant_1098: 2018-03-04 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:2017-10-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Tunisian Collegiate Training Contest - Round #01