You are given a graph with N vertices (numbered 1 to N) and M bidirectional edges, which doesn't contain multiple edges or self-loops — that is, the given graph is a simple undirected graph.

For each pair of vertices a, b such that 1 ≤ a, b ≤ N, it is possible to add a new edge between vertices a and b to the graph, with a cost of (a - b)^2.

Find the minimum cost of adding edges so that vertex N is reachable from vertex 1.

------ Input Format ------

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains 2 space-separated integers, N and M.
• The i^{th} of the next M lines contains 2 space-separated integers u_{i} and v_{i}, denoting a bidirectional edge between vertex u_{i} and vertex v_{i} in the graph.

------ Output Format ------

For each test case, output the answer in a single line.

------ Constraints ------

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ M ≤ 2 \cdot 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
- The graph doesn't contain self-loops or multiple edges
- Sum of $N$ over all testcases is no more than $2 \cdot 10^{5}$.
- Sum of $M$ over all testcases is no more than $2 \cdot 10^{5}$.

----- Sample Input 1 ------
3
2 0
5 4
3 2
1 4
5 3
4 2
6 3
1 2
3 2
1 3

----- Sample Output 1 ------
1
0
3

----- explanation 1 ------
Test Case $1$: Add an edge between vertices $1$ and $2$, with cost $(1-2)^2 = 1$.

Test Case $2$: Vertices $1$ and $5$ are already connected, so no edges need to be added.

见题面

见题面