O. Minimum Diameter Queries
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Litusiano was listening to La Mafia Del Amor when he came up with the following problem:

You are given $$$n$$$ trees, where the $$$i$$$-th tree has $$$m_i$$$ nodes. You need to answer $$$q$$$ queries.

Each query consists of two integers $$$l$$$ and $$$r$$$. For each query, you are asked to find the minimum diameter of the resulting tree if you optimally merge all the trees in the range $$$[l, r]$$$.

To merge two trees, you add exactly one edge between a node from each tree. Refer to the sample explanation for a better understanding of the merging process.

Note: The diameter of a tree is defined as the longest path between any two nodes in the tree.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 2024$$$). The description of the test cases follows.

For each test case:

The first line consists of a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) — the number of trees.

Then follows the representation of the $$$n$$$ trees. For each tree:

  • The first line consists of one integer $$$m_i$$$ ($$$1 \leq m_i \leq 2 \cdot 10^{5}$$$) — the number of nodes of the $$$i$$$-th tree.
  • Then follow $$$m_i - 1$$$ lines, each one consisting of two integers $$$u$$$, $$$v$$$ ($$$1 \leq u, v \leq m_i$$$) — the edges of the $$$i$$$-th tree.

After the representation of all the trees, a line will follow with one integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^{5}$$$) — the number of queries.

The following $$$q$$$ lines will contain two integers $$$l$$$, $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) — the ranges for the queries.

It is guaranteed that the sum of $$$n$$$, $$$m_i$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output

For each query, output the minimum diameter of the resulting tree if you merge optimally all the trees in the range $$$[l, r]$$$.

Example
Input
2
2
3
1 2
2 3
4
1 2
1 3
1 4
1
1 2
1
2
1 2
1
1 1
Output
4
2
Note

In the first test case, the answer to the query is 4 because if you add an edge between node $$$2$$$ of the first tree and node $$$1$$$ of the second tree, the diameter is $$$4$$$, and it's impossible to merge both trees in such a way that results in a smaller diameter.