Optimal Delivery Center

In Bob's city, there are \(n\) post offices connected by \(n-1\) weighted undirected edges forming a tree. Bob has to deliver \(m\) packages. For the \(i\)-th package, he needs to deliver from node \(u_i\) to node \(v_i\). To ensure that he does not carry a package too far, for each delivery he will start at the delivery center \(c\), travel to \(u_i\), return to \(c\), go from \(c\) to \(v_i\), and then return to \(c\). In other words, his route for the \(i\)-th package is

[ c \rightarrow u_i \rightarrow c \rightarrow v_i \rightarrow c ]

The distance for one delivery is given by:

[ D_i(c) = d(c, u_i) + d(c, v_i) ]

where \(d(a,b)\) is the distance between nodes \(a\) and \(b\) in the tree. Note that the complete route costs twice this value, but it is guaranteed to be even so that you only need to output \(D_i(c)\) for the worst delivery.

Bob wants to choose a node \(c\) as the delivery center so that the maximum delivery distance over all packages,

[ F(c) = \max_{1 \le i \le m} [d(c,u_i) + d(c,v_i)], ]

is minimized. Find the optimal \(c\) (you do not need to output \(c\) itself) and output the minimized maximum value \(\min_{c} F(c)\).

inputFormat

The first line contains an integer \(n\) \( (1 \leq n \leq 2000)\), the number of post offices.

Each of the next \(n-1\) lines contains three integers \(u\), \(v\) and \(w\) indicating there is an edge between nodes \(u\) and \(v\) with weight \(w\) (\(1 \leq w \leq 10^6\)).

The next line contains an integer \(m\) \( (1 \le m \le 2000)\), the number of deliveries.

Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) representing a delivery from \(u_i\) to \(v_i\).

outputFormat

Output a single integer: the minimized maximum delivery distance divided by 2, i.e. \(\min_{c} \max_{1 \le i \le m} [d(c,u_i)+d(c,v_i)]\).

sample

3
1 2 1
2 3 1
1
1 3

2