Farmer John 的農場由 $N$ 塊田地 $(1 \leq N \leq 10^5)$ 組成，方便起見，編號為 $1 \ldots N$。這些田地之間有 $M$ 條雙向道路 $(0 \leq M \leq 10^5)$，每條道路連接兩塊田地。

農場裡有兩座牛棚，一座位於田地 $1$，另一座位於田地 $N$。Farmer John 希望確保能沿著一系列道路在兩座牛棚之間行走。他願意為此最多修建兩條新道路。由於田地的位置分布，在田地 $i$ 和 $j$ 之間修建一條新道路的費用為 $(i-j)^2$。

請幫助 Farmer John 求出使牛棚 $1$ 和 $N$ 相互可達所需的最小費用。

輸入格式

每個輸入測試點包含 $T$ 組子測試資料 ($1\le T\le 20$)，必須正確解決所有子測試資料才能通過該輸入測試點。

輸入的第一行包含 $T$，隨後給出 $T$ 組子測試資料。

每組子測試資料以兩個整數 $N$ 和 $M$ 開始。接下來 $M$ 行，每行包含兩個整數 $i$ 和 $j$，表示兩塊不同的田地 $i$ 和 $j$ 之間的一條道路。保證任意兩塊田地之間最多有一條道路，且所有子測試資料的 $N+M$ 之和不超過 $5 \cdot 10^5$。

輸出格式

輸出 $T$ 行。第 $i$ 行應包含一個整數，表示第 $i$ 組子測試資料的最小費用。

範例

輸入格式 1

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

輸出格式 1

2
1

說明

在第一組子測試資料中，最佳方案是用一條道路連接田地 $2$ 和 $3$，再用一條道路連接田地 $3$ 和 $4$。

在第二組子測試資料中，最佳方案是用一條道路連接田地 $3$ 和 $4$。不需要第二條道路。

子任務

• 測試點 2 滿足 $N \le 20$。
• 測試點 3-5 滿足 $N \le 10^3$。
• 測試點 6-10 沒有額外限制。

題目作者：Nick Wu