Farmer John の農場は $N$ 個の畑 $(1 \leq N \leq 10^5)$ からなり、便宜上 $1 \ldots N$ と番号が付けられています。これらの畑の間には $M$ 本の双方向の道 $(0 \leq M \leq 10^5)$ があり、それぞれが 2 つの畑を結んでいます。

農場には 2 つの牛舎があり、一方は畑 $1$ に、もう一方は畑 $N$ にあります。Farmer John は、一連の道を歩いて 2 つの牛舎の間を移動できるようにしたいと考えています。このために新しい道を最大 2 本造るつもりです。畑の配置により、畑 $i$ と $j$ の間に新しい道を造る費用は $(i-j)^2$ です。

牛舎 $1$ と $N$ を互いに到達可能にするために必要な最小費用を求め、Farmer John を助けてください。

入力

各入力テストケースは $T$ 個のサブテストケース ($1\le T\le 20$) を含み、その入力テストケースを正解するにはすべてを正しく解く必要があります。

入力の最初の行には $T$ が与えられ、その後に $T$ 個のサブテストケースが続きます。

各サブテストケースは 2 つの整数 $N$ と $M$ で始まります。その後に $M$ 行が続き、各行には 2 つの整数 $i$ と $j$ が与えられ、異なる 2 つの畑 $i$ と $j$ の間の道を表します。任意の 2 つの畑の間には道が高々 1 本あり、すべてのサブテストケースにわたる $N+M$ の総和は $5 \cdot 10^5$ 以下であることが保証されます。

出力

$T$ 行出力してください。$i$ 行目には、$i$ 番目のサブテストケースの最小費用を表す 1 つの整数を出力してください。

入出力例

入力 1

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

出力 1

2
1

注記

最初のサブテストケースでは、畑 $2$ と $3$ を道で結び、畑 $3$ と $4$ を道で結ぶのが最適です。

2 番目のサブテストケースでは、畑 $3$ と $4$ を道で結ぶのが最適です。2 本目の道は必要ありません。

小課題

• テストケース 2 は $N \le 20$ を満たします。
• テストケース 3-5 は $N \le 10^3$ を満たします。
• テストケース 6-10 には追加の制約はありません。

問題作成：Nick Wu