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 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?

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 weight.

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
sleepntsheep: 2023-04-22 15:02:13

nice problem

mastercopycode: 2021-07-02 17:06:22

This is good problems and I like to eat dog feces.

Last edit: 2021-07-03 01:49:24
shreyas_07: 2020-10-16 03:38:28

Use path compression as well along with DSU

abhishak69: 2020-03-25 04:38:52

offline queries + dsu

nadstratosfer: 2020-03-21 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: 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.

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.


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