3631. 连接两个谷仓

【题目描述】

Farmer John 的农场由N块田地（1≤N≤10^5）组成，编号为1...N。在这些田地之间有M条双向道路（0≤M≤10^5），每条道路连接两块田地。农场有两个牛棚，一个在田地1中，另一个在田地N中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。 他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地i和j之间建造新道路的花费是(i−j)^2。

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

【输入格式】

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

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

每个子测试用例的第一行包含两个整数N和M。以下M行，每行包含两个整数i和j，表示一条连接两个不同田地i和j的道路。输入保证任何两个田地之间至多只有一条道路，并且所有子测试用例的N+M之和不超过 5*10^5。

【输出格式】

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

【样例输入】

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

【样例输出】

2
1

【样例说明】

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

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

【数据规模与约定】

测试点 2 满足 N≤20。测试点 3-5 满足 N≤10^3。

测试点 6-10 没有额外限制

【来源】

USACO 2021.12 银组第二题