题目描述

Farmer John 的农场由 $N$ 块田地组成，编号为$1...N$。

在这些田地之间有 $M$ 条双向道路，每条道路连接两块田地。

农场有两个牛棚，一个在田地 $1$ 中，另一个在田地 $N$ 中。

Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。

他愿意建造至多两条新道路来实现这一目标。

由于田地的位置因素，在田地 $i$ 和 $j$ 之间建造新道路的花费是$(i-j)^2$ 。

请帮助 Farmer John 求出使得牛棚 $1$ 和 $N$ 可以相互到达所需要的最小花费。

输入格式

每个测试用例的输入包含 $T$ 个子测试用例，所有子测试用例必须全部回答正确才能通过整个测试用例。

输入的第一行包含 $T$，之后是 $T$ 个子测试用例。

每个子测试用例的第一行包含两个整数 $N$ 和 $M$。

以下 $M$ 行，每行包含两个整数 $i$ 和 $j$，表示一条连接两个不同田地 $i$ 和 $j$ 的道路。

输出格式

输出 $T$ 行。第 $i$行包含一个整数，为第 $i$ 个子测试用例的最小花费。

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

2
1

提示

$1≤T≤20,$
$1≤N≤10^5,$
$0≤M≤10^5,$
输入保证任何两个田地之间至多只有一条道路，并且所有子测试用例的 $N+M$ 之和不超过 $5×10^5$。

样例解释

第一个子测试用例中，最优的方式是用一条道路连接田地 $2$ 和 $3$，用一条道路连接田地 $3$ 和 $4$。

第二个子测试用例中，最优的方式是用一条道路连接田地 $3$ 和 $4$。不需要第二条道路。