Connecting Two Barns

题目描述

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$ 个子测试用例的最小代价。

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

2
1

提示

在第一个子测试用例中，最优做法是连接田地 2 和 3，并连接田地 3 和 4。 在第二个子测试用例中，最优做法是连接田地 3 和 4。不需要第二条路径。 SCORING: 测试点 2 满足 $N \le 20$。 测试点 3-5 满足 $N \le 10^3$。 测试点 6-10 没有额外限制。 题目来源：Nick Wu

标签: USACO|2021|Silver

来源

USACO|2021|Silver