Connecting Two Barns

문제

Farmer John's farm consists of a set of $NN$ fields $(1\le N\le {10}^5)(1\; \backslash leq\; N\; \backslash leq\; 10^5)$, conveniently numbered $1\dots N1\; \backslash ldots\; N$. Between these fields are $MM$ bi-directed paths $(0\le M\le {10}^5)(0\; \backslash leq\; M\; \backslash leq\; 10^5)$, each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field $NN$. 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 $ii$ and $jj$ is $(i-j{)}^2(i-j)^2$.

Please help Farmer John determine the minimum cost needed such that barns $11$ and $NN$ become reachable from each-other.

입력

Each input test case contains $TT$ sub-cases ($1\le T\le 201\backslash le\; T\backslash le\; 20$), all of which must be solved correctly to solve the input case.

The first line of input contains $TT$, after which $TT$ sub-test cases follow.

Each sub-test case starts with two integers, $NN$ and $MM$. Next, $MM$ lines follow, each one containing two integers $ii$ and $jj$, indicating a path between two different fields $ii$ and $jj$. It is guaranteed that there is at most one path between any two fields, and that the sum of $N+MN+M$ over all sub-test cases is at most $5\cdot {10}^{5}5\; \backslash cdot\; 10^5$.

출력

Output $TT$ lines. The $ii$th line should contain a single integer giving the minimum cost for the $ii$th sub-test case.

2
5 2
1 2
4 5
5 3
1 2
2 3
4 5

2
1