Festivals

All submissions for this problem are available.
The Chef is enjoying his vacation at the Tree city. As the name of it says, in this city, N locations, numbered from 1 to N, are connected by N − 1 bidirectional roads. Each road connects two cities and you can travel between any pair of cities through this roads system. Each road has the length, which is some positive integer. For any two locations the distance between them is the sum of the roads lengths for the path that connects them.
Some festivals are regularly held in each location. Someday, several festivals (at least 2) take place at different locations. On that day people often participate in two festivals such that the distance between their locations is as large as possible. They move between these two locations to enjoy the festivals. Note that there may be more than one pair of locations satisfying this condition. The path connecting two such locations is called an ideal path.
Knowing this, the Chef wants to find an optimal road where he will open temporary fastfood restaurant to earn as much money as possible from hungry festival participants that move by this road. In his honest opinion the best such road is the shortest road belonging to each ideal path.
More formally he is asking you two questions as follows. Suppose in day X, there are K festivals that take place at K locations F_{1}, F_{2}, ..., F_{K} respectively.
 Find the distance between two furthest locations among the K locations listed above. Denote this value as A.
 Find the road with the minimal length belonging to each ideal path. That is, each path of length A, that connects F_{i} and F_{j} for some i and j, should contain this road. Denote the length of this road as B. If there is no such road than B is set to 1.
 Of course, Chef wants to know values A and B.
Input
The first line of the input contains a single integer N, denoting the overall number of locations in the Tree city. Each of the following N − 1 lines describes a road and contains three spaceseparated integers U, V and C, which means that the road of length C connects locations U and V.
The next line contains a single integer Q, denoting the number of questions Chef is asking you. Each of the following Q lines describes a question and contains an integer K followed by K space separated integers F_{1}, F_{2}, ..., F_{K}, denoting the locations where the festivals take place.
Output
For each question, output on a separate line two spaceseparated integers A and B. Their meaning is described above.
Constraints
 1 ≤ N ≤ 100000 (10^{5})
 1 ≤ U, V ≤ N
 U ≠ V
 1 ≤ C ≤ 10000 (10^{4})
 It is guaranteed that the roads in the input describe a tree of N vertexes
 1 ≤ Q ≤ 100000 (10^{5})
 2 ≤ K ≤ N
 1 ≤ F_{1}, F_{2}, ..., F_{K} ≤ N
 F_{1}, F_{2}, ..., F_{K} are different
 The sum of K over the input does not exceed 200000 (2 * 10^{5})
Example
Input: 6 1 2 3 1 4 2 1 5 2 2 3 3 2 6 3 2 2 2 5 4 3 4 5 6 Output: 5 2 8 3
Explanation
Example question 1. The only ideal path is between 2 and 5. This path contains two roads: (5, 1) and (1, 2); and (5, 1) is the shortest road among them.
Example question 2. The ideal paths are between the following pairs: (3 and 4), (4 and 6), (5 and 3), and (5 and 6). Only road (1, 2) belongs to each ideal path.
Author:  tuananh93 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/SUBTREE 
Tags  lca, march13, medium, tree, tuananh93 
Date Added:  25122012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 