#P7991. [USACO21DEC] Connecting Two Barns S

[USACO21DEC] Connecting Two Barns S

题目描述

Farmer John 的农场由 NN 块田地(1N1051 \leq N \leq 10^5)组成,编号为 1N1 \ldots N。在这些田地之间有 MM 条双向道路(0M1050 \leq M \leq 10^5),每条道路连接两块田地。

农场有两个牛棚,一个在田地 1 中,另一个在田地 NN 中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。 他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素,在田地 iijj 之间建造新道路的花费是 (ij)2(i-j)^2

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

输入格式

每个测试用例的输入包含 TT 个子测试用例(1T201\le T\le 20),所有子测试用例必须全部回答正确才能通过整个测试用例。

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

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

输出格式

输出 TT 行。第 ii 行包含一个整数,为第 ii 个子测试用例的最小花费。

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

提示

【样例解释】

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

【数据范围】

  • 测试点 2 满足 N20N \le 20
  • 测试点 3-5 满足 N103N \le 10^3
  • 测试点 6-10 没有额外限制。