Limits 3s, 1.0 GB

Have you ever heard of The Atlantis City? It’s a Greek mythological city. Its existence doesn’t matter to us anymore. But last night I had a nightmare. Poseidon, The King of Great Atlantis City, came to me and gave me a problem. Now you must write a program that can solve the Poseidon problem.

Atlantis City consists of N number of forts. They are connected by N-1 number of roads. Fort 1 is The Palace of King Poseidon. There is a soldier in every fort. For traveling each road, a transport cost has to be paid. This payment has to be made by coins. But there’s a strange rule in Atlantis city. Every fort can keep only one type of coin. Now Poseidon wants to know if fort f have p valued coin, what is the nearest fort from the palace where a soldier of fort f can reach.

Now for each query, your program should receive two integers f, p and print a fort number v which is the nearest from The Palace and can travel from f to v using only p valued coin. You can assume that there are unlimited numbers of p valued coin in fort f.

Poseidon said that he would come tonight in every contestant’s dream and ask for a program which can answer the query. So Hurry Up!

Input

First Line consists of an integer T (1 ≤ T ≤ 5), number of test cases.

Each test case starts with an integer N (2 ≤ N ≤ 100000), the number of forts in Atlantis city. Next N-1 lines, each line contains three integers u, v (1 ≤ u, v, f ≤ N), w (1 ≤ w ≤ 10000000), where there is a road in u and v; w is the traveling cost of this road.

Then there’s one integer q (2 ≤ q ≤ 100000), number of queries. Next q lines each contains two integer f (1 ≤ f ≤ N), p (1 ≤ p ≤ 10000000) where f is the fort number and p is the value of the coin.

Output

At first print case number. For each query, you should print a line containing fort number which is the nearest fort from The Palace and can reach from f using p valued coin. For detailed output format, please see sample output.

Samples

InputOutput
1						
4
1 2 10
1 3 7
4 3 14
3
2 5
4 7
4 10
Case 1:
1
1
4
InputOutput
1
5
1 2 2
1 3 7
3 4 10
5 4 15
2
5 5
2 1
Case 1:
3
1

Submit

Login to submit.

Contributors

Statistics

87% Solution Ratio
IOI_StfuFfsEarliest, May '18
Takik_Fastest, 0.0s
experimenterLightest, 25 MB
IOI_StfuFfsShortest, 1178B
Toph uses cookies. By continuing you agree to our Cookie Policy.