#PU1159. USACO 2021 December Contest, Silver — Problem 2. Connecting Two Barns

USACO 2021 December Contest, Silver — Problem 2. Connecting Two Barns

USACO 2021 December Contest, Silver — Problem 2. Connecting Two Barns

题目描述

Farmer John's farm consists of a set of NN fields (1≤N≤105)(1 \leq N \leq 10^5), conveniently numbered 1…N1 \ldots N. Between these fields are MM bi-directed paths (0≤M≤105)(0 \leq M \leq 10^5), each connecting a pair of fields. The farm contains two barns, one in field 1 and the other in field NN. Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields ii and jj is (i−j)2(i-j)^2. Please help Farmer John determine the minimum cost needed such that barns 11 and NN become reachable from each-other.

输入格式

Each input test case contains TT sub-cases (1≤T≤201\le T\le 20), all of which must be solved correctly to solve the input case. The first line of input contains TT, after which TT sub-test cases follow. Each sub-test case starts with two integers, NN and MM. Next, MM lines follow, each one containing two integers ii and jj, indicating a path between two different fields ii and jj. It is guaranteed that there is at most one path between any two fields, and that the sum of N+MN+M over all sub-test cases is at most 5⋅1055 \cdot 10^5.

输出格式

(见题面原文)

数据范围

Test case 2 satisfies N≤20N \le 20. Test cases 3-5 satisfy N≤103N \le 10^3. Test cases 6-10 satisfy no additional constraints. Problem credits: Nick Wu

样例

样例 1

2
5 2
1 2
4 5
5 3
1 2
2 3
4 5
2
1
In the first sub-test case, it is optimal to connect fields 2 and 3 with a 
path, and fields 3 and 4 with a path.
In the second sub-test case, it is optimal to connect fields 3 and 4 with a
path.  No second path is needed.