You are given the description of TeddyLand, an undirected tree of $n$ nodes where each node represent a TeddyCity, and there's a TeddyPerson that lives in each of the TeddyCities.
As everyone knows, since the TeddyBearsDay is approaching, people from all around TeddyLand are planning to send TeddyBears to each other.
But we all know that the TeddyDelivery is very expensive these days (the TeddyCost to send a TeddyBear from a TeddyCity to another TeddyCity is the length of the TeddyPath between them!).
So you, the TeddyKing, will rearrange the TeddyDeliveries in such a way that each TeddySender will still send the same amount of TeddyBears, and each TeddyReceiver will still receive the same amount of TeddyBears, and the total TeddyCost is minimum.
The first line will contain one integer $T$ $(1 <= T <= 250)$ - the number of TeddyTestCases.
The first line of each TeddyCase will contain one integer $n$ $(1 <= n <= 10000)$ - the number of TeddyCities in TeddyLand.
The following $n -1$ lines will contain three integers each $u_i$ , $v_i$ and $w_i$ $(1 <= u_i, v_i <= n)$ $(1 <= w_i <= 10000)$ - meaning that TeddyCity $u_i$ is connected to TeddyCity $v_i$ with a TeddyRoad of length $w_i$.
The next line will contain one integer $q$ $(1 <= q <= 10000)$ - the number of TeddyDeliveries planned.
The following $q$ lines will contain two integers each $u_i$ , $v_i$ $(1 <= u_i, v_i <= n)$ - meaning that the TeddyPerson in TeddyCity $u_i$ wants to send a TeddyBear for the TeddyPerson that lives in the TeddyCity $v_i$.
It's possible that $u_i$ is equal to $v_i$.
The total sum of $n <= 5 * 10^5$
The total sum of $q <= 5 * 10^5$
For each test case, output a single line with the minimum total TeddyCost of all TeddyDeliveries after rearrangement.
## Input
The first line will contain one integer $T$ $(1 <= T <= 250)$ - the number of TeddyTestCases.The first line of each TeddyCase will contain one integer $n$ $(1 <= n <= 10000)$ - the number of TeddyCities in TeddyLand.The following $n -1$ lines will contain three integers each $u_i$ , $v_i$ and $w_i$ $(1 <= u_i, v_i <= n)$ $(1 <= w_i <= 10000)$ - meaning that TeddyCity $u_i$ is connected to TeddyCity $v_i$ with a TeddyRoad of length $w_i$.The next line will contain one integer $q$ $(1 <= q <= 10000)$ - the number of TeddyDeliveries planned.The following $q$ lines will contain two integers each $u_i$ , $v_i$ $(1 <= u_i, v_i <= n)$ - meaning that the TeddyPerson in TeddyCity $u_i$ wants to send a TeddyBear for the TeddyPerson that lives in the TeddyCity $v_i$. It's possible that $u_i$ is equal to $v_i$.The total sum of $n <= 5 * 10^5$ The total sum of $q <= 5 * 10^5$
## Output
For each test case, output a single line with the minimum total TeddyCost of all TeddyDeliveries after rearrangement.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ be the number of nodes (TeddyCities).
- Let $ G = (V, E) $ be an undirected tree with $ V = \{1, 2, \dots, n\} $, and edge set $ E $, where each edge $ (u_i, v_i) \in E $ has weight $ w_i \in \mathbb{Z}^+ $.
- Let $ d(u, v) $ denote the shortest path distance (sum of edge weights) between nodes $ u $ and $ v $ in $ G $.
- Let $ q \in \mathbb{Z} $ be the number of planned deliveries.
- Let $ D = \{(s_j, t_j) \mid j \in \{1, \dots, q\}\} $ be the multiset of delivery requests, where $ s_j, t_j \in V $.
**Constraints**
1. $ 1 \le T \le 250 $
2. $ 1 \le n \le 10000 $, $ \sum n \le 5 \times 10^5 $
3. $ 1 \le w_i \le 10000 $
4. $ 1 \le q \le 10000 $, $ \sum q \le 5 \times 10^5 $
5. $ 1 \le s_j, t_j \le n $ for all $ j $
**Objective**
Minimize the total cost of reassigning deliveries such that:
- The number of deliveries originating from each node $ u $ remains unchanged (i.e., the out-degree multiset is preserved).
- The number of deliveries received at each node $ v $ remains unchanged (i.e., the in-degree multiset is preserved).
That is, let $ f: D \to D $ be a bijection (rearrangement) such that:
- $ |\{ j \mid s_j = u \}| = |\{ j \mid f(s_j, t_j) = (u, t') \}| $ for all $ u \in V $,
- $ |\{ j \mid t_j = v \}| = |\{ j \mid f(s_j, t_j) = (s', v) \}| $ for all $ v \in V $.
Minimize:
$$
\sum_{j=1}^q d(s_j', t_j')
$$
where $ f((s_j, t_j)) = (s_j', t_j') $.
**Note**: This is equivalent to finding a minimum-cost bipartite matching between the multiset of senders and receivers, where the cost between sender $ u $ and receiver $ v $ is $ d(u, v) $, and the supply at each node $ u $ equals the number of times $ u $ appears as a source in $ D $, and the demand at each node $ v $ equals the number of times $ v $ appears as a target in $ D $.