Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Poltu and Graph

By RamprosadG · Limits 1s, 512 MB

Poltu has got a graph with N nodes and M edges. Every edge has a weight. There can be multiple edges between two nodes. He gave his friend Boltu some query on this graph. In each query, he gave his friend two integers V and X. How many distinct node Boltu can visit if he starts his journey from the node V and if he can’t use the edge whose weight is greater than X.

In the journey he can use any node and any edge multiple times.

Input

The input will start with two integers N (1 ≤ N ≤ 200000), number of nodes and M (0 ≤ M ≤ 200000), number of edges.

The next M lines will contains three integer U, V (1 ≤ U, V ≤ N and U ≠ V), W, that is an undirected edge between U and V, whose weight is W (1 ≤ W ≤ 1000000000).

Then the following line contains an Integer Q (1 ≤ Q ≤ 200000), the number of queries.

The next Q lines will contain two integers V and X (1 ≤ X ≤ 1000000000).

Output

For each query you have to print the number of nodes he can visit by maintaining the above rules in separate line.

Sample

InputOutput
5 5
1 2 5
1 3 4
2 3 7
3 4 6
4 5 1
4
1 7
1 5
1 3
4 5 
5
3
1
2

Dataset is huge, please use faster input/output.

Discussion

Statistics


82% Solution Ratio

kzvd4729Earliest, Dec '19

agtxdyFastest, 0.1s

Riaz_BSMRSTULightest, 8.5 MB

kzvd4729Shortest, 929B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.