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!
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.
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.
Input | Output |
---|---|
1 4 1 2 10 1 3 7 4 3 14 3 2 5 4 7 4 10 | Case 1: 1 1 4 |
Input | Output |
---|---|
1 5 1 2 2 1 3 7 3 4 10 5 4 15 2 5 5 2 1 | Case 1: 3 1 |