SP12866 NTICKETS - Nlogonian Tickets

You live in Nlogonia, a country that has N cities connected by some bidirectional roads (as usual). In Nlogonia, there is exactly one path between any pair of cities. You can't use the roads during your travels for free. There is an officer at each road that will let you use it only if you show him a certain number of tickets. If you don't have the required amount of tickets, you just can't use that road. The officer will not keep the tickets, though. You need to show the tickets to him, but you can keep them after that. This indicates that you can use the same ticket in more than one road, if you want to. You are given a description of the road system of Nlogonia and a number of queries. For each query, find the minimum number of tickets you must have to go from a city A to a city B. Consider that city A is the only place where you can buy tickets, so you must be holding all the tickets you will need during the travel before leaving city A.

Each test case starts with a line containing the integer N (2 Each of the next N-1 lines contains the description of a road, A B T (1 The next line contains the integer Q (1 The last test case is followed by a line containg the number 0.

For each query A B, print the minimum number of tickets needed during the travel from city A to city B. Print a blank line after each test case.