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
| Input | Output |
|---|---|
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.
