Connecting Two Barns#11223
Farmer John's farm consists of a set of fields, conveniently numbered . Between these fields are bidirected paths, each connecting a pair of fields.
The farm contains two barns, one in field and the other in field . Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields and is (i - j)^2.
Please help Farmer John determine the minimum cost needed such that barns and become reachable from each other.
The first line contains the number of test cases (1 \le t \le 20).
Each sub-test case starts with two integers (1 \le n \le 10^5) and (0 \le m \le 10^5). Next, lines follow, each one containing two integers and , indicating a path between two different fields and . It is guaranteed that there is at most one path between any two fields, and that the sum of n + m over all sub-test cases is at most 5 \cdot 10^5.
Output lines. The -th line should contain a single integer giving the minimum cost for the ith sub-test case.
Example 1
In the first test case, it is optimal to connect fields and with a path, and fields and with a path.
In the second test case, it is optimal to connect fields and with a path. No second path is needed.