Description

Farmer John's farm consists of a set of $N$ fields,conveniently numbered $1 \ldots N$. Between these fields are $M$ bi-directedpaths, each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field $N$. FarmerJohn would like to ensure that there is a way to walk between the two barnsalong some series of paths. He is willing to build up to two new paths toaccomplish this goal. Due to the way the fields are situated, the cost ofbuilding a new path between fields $i$ and $j$ is $(i-j)^2$.

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

• $1 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$

Input Format

Each input test case contains $T$ sub-cases, all of which mustbe solved correctly to solve the input case.

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

Each sub-test case starts with two integers, $N$ and $M$. Next, $M$ linesfollow, each one containing two integers $i$ and $j$, indicating a path betweentwo different fields $i$ and $j$. It is guaranteed that there is at most onepath between any two fields, and that the sum of $N+M$ over all sub-test casesis at most $5 \cdot 10^5$.

• $1\le T\le 20$

Output Format

Output $T$ lines. The $i$th line should contain a single integer giving theminimum cost for the $i$th sub-test case.

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

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

Scoring

• Test case 2 satisfies $N \le 20$.
• Test cases 3-5 satisfy $N \le 10^3$.
• Test cases 6-10 satisfy no additional constraints.

Problem Credit

Problem credits: Nick Wu