405469: GYM101968 E Connecting Components

You are given an undirected graph with $$$n$$$ nodes and $$$n-1$$$ edges. The graph doesn't contain loops or multiple edges.

You are allowed to make the following operation at most twice:

• Choose an edge ($$$u$$$, $$$v$$$) from the graph, change it to ($$$u$$$, $$$w$$$), the cost of this operation is $$$|w-v|$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

  In other words, you are allowed to change one endpoint of an edge in one move, and the cost of this move is the absolute difference between the new ID and the old ID of the changed endpoint.

Find the minimum total cost needed to make the given graph connected in at most two moves, or determine that it is impossible.

Note that you do not have to minimize the number of moves.

The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$), the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of nodes in the graph.

Each of the following $$$n-1$$$ lines contains two space-separated integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), representing an edge that connects the nodes $$$u$$$ and $$$v$$$. Each pair of nodes will be connected by at most one edge.

The sum of $$$n$$$ over all test cases doesn't exceed $$$5\times10^6$$$.

For each test case, if it is impossible to make the given graph connected in at most two moves, output $$$-1$$$. Otherwise, output the minimum total cost needed, in a single line.

3
8
5 1
1 3
3 5
4 2
2 7
7 6
6 2
2
1 2
7
1 2
1 3
1 4
2 3
2 4
3 4

2
0
-1