时间限制：1秒　　内存限制：256M

---

【问题描述】

　　FJ 的牧场由 \(N\) 块草地组成，编号为 \(1..N\)。在这些草地之间有 \(M\) 条双向道路，每条道路连接两块草地。

　　牧场里有两个牛棚，一个在草地 1 中，另一个在草地 \(N\) 中。FJ 希望至少有一条能在两个牛棚之间行走路径（即草地1和N之间能连通）。但是最初给出的 \(M\) 条双向道路无法保证 \(1\) 和 \(N\) 能相互到达，因此FJ想再建造至多两条新的双向道路来实现这一目标。由于草地的位置因素，若在草地 \(a\) 和 \(b\) 之间建造新道路，需要的花费是 \((a−b)^2\)。

　　请帮助 FJ 求出使得牛棚 1和 \(N\) 可以相互到达所需要的最小花费。

【输入格式】

　　输入的第一行包含 \(T（1≤T≤20）\)，之后是 \(T\) 组数据。
　　每组数据的第一行包含两个整数 \(N\) 和 \(M\)。以下 \(M\) 行，每行包含两个整数 \(u\) 和 \(v\)，表示一条连接两个不同草地 \(u\) 和 \(v\) 的双向道路。输入保证任何两个草地之间至多只有一条道路，并且所有子测试用例的 \(N+M\) 之和不超过500000。

【输出格式】

　　输出 \(T\) 行。第 \(i\) 行包含一个整数，为第 \(i\) 组数据的最小花费。

【输入输出样例】

　Input

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

　Output

2
1

【样例说明】

　　第一组数据中，最优的方式是：在草地 2 和 3之间修一条路，在草地 3 和 4之间修一条路，总花费为(2-3)2 + (3-4)2 = 2。
　　第二组数据中，最优的方式是：在草地 3 和 4之间修一条路，不需要第二条道路，花费为 (3-4)2 = 1。

【数据说明】

　　测试点 2 满足 \(N≤20\)。
　　测试点 3-5 满足 \(N≤10^3\)。
　　测试点 6-10 满足 \(N,M≤10^5\)。

【来源】

　　Mr.he