Problem Description

Farmer John’s farm consists of $N$ fields ($1 \leq N \leq 10^5$), numbered $1 \ldots N$. There are $M$ bidirectional roads ($0 \leq M \leq 10^5$) between the fields, and each road connects two fields.

There are two barns on the farm: one in field $1$ and the other in field $N$. Farmer John wants to make sure there is a way to walk between the two barns along some sequence of roads. He is willing to build at most two new roads to achieve this. Because of the fields’ locations, the cost to build a new road between fields $i$ and $j$ is $(i-j)^2$.

Please help Farmer John find the minimum cost needed to make barns $1$ and $N$ reachable from each other.

Input Format

The input of each test file contains $T$ subtasks ($1 \le T \le 20$). You must answer all subtasks correctly to pass the entire test file.

The first line contains $T$, followed by $T$ subtasks.

For each subtask, the first line contains two integers $N$ and $M$. The next $M$ lines each contain two integers $i$ and $j$, indicating a road connecting two different fields $i$ and $j$. The input guarantees that there is at most one road between any pair of fields, and the sum of $N+M$ over all subtasks does not exceed $5 \cdot 10^5$.

Output Format

Output $T$ lines. The $i$-th line contains one integer, the minimum cost for the $i$-th subtask.

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

2
1

Hint

[Sample Explanation]

• In the first subtask, the best way is to build one road connecting fields $2$ and $3$, and one road connecting fields $3$ and $4$.
• In the second subtask, the best way is to build one road connecting fields $3$ and $4$. A second road is not needed.

[Constraints]

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

Translated by ChatGPT 5