405469: GYM101968 E Connecting Components

Memory Limit:256 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Connecting Componentstime limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$$$.

Output

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.

ExampleInput
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
Output
2
0
-1

加入题单

上一题 下一题 算法标签: