USACO 2019 US Open Contest, Silver Problem 3 Fence Planning

Farmer John's?NN?cows, conveniently numbered?1…N1…N?(2≤N≤1052≤N≤105), have a complex social structure revolving around "moo networks" --- smaller groups of cows that communicate within their group but not with other groups.

Each cow is situated at a distinct?(x,y)(x,y)?location on the 2D map of the farm, and we know that?MM?pairs of cows?(1≤M<105)(1≤M<105)moo at each-other. Two cows that moo at each-other belong to the same moo network.

In an effort to update his farm, Farmer John wants to build a rectangular fence, with its edges parallel to the?xx?and?yy?axes. Farmer John wants to make sure that at least one moo network is completely enclosed by the fence (cows on the boundary of the rectangle count as being enclosed). Please help Farmer John determine the smallest possible perimeter of a fence that satisfies this requirement. It is possible for this fence to have zero width or zero height.

INPUT FORMAT (file fenceplan.in):

The first line of input contains?NN?and?MM. The next?NN?lines each contain the?xx?and?yy?coordinates of a cow (nonnegative integers of size at most?108108). The next?MM?lines each contain two integers?aa?and?bb?describing a moo connection between cows?aa?and?bb. Every cow has at least one moo connection, and no connection is repeated in the input.

OUTPUT FORMAT (file fenceplan.out):

Please print the smallest perimeter of a fence satisfying Farmer John's requirements.

SAMPLE INPUT:
7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 6

SAMPLE OUTPUT:
10

Problem credits: Brian Dean

---

中文版

Farmer John的NN頭奶牛，編號為1…N1…N（2≤N≤1052≤N≤105），擁有一種圍繞“哞網”，一些僅在組內互相交流卻不與其他組進行交流的奶牛小組，組成的復雜的社交網絡。

每頭奶牛位于農場的二維地圖上的不同位置(x,y)(x,y)，并且我們知道有MM對奶牛(1≤M<105)(1≤M<105)會相互哞叫。兩頭相互哞叫的奶牛屬于同一哞網。

為了升級他的農場，Farmer John想要建造一個四邊與xx軸和yy軸平行的長方形圍欄。Farmer John想要使得至少一個哞網完全被圍欄所包圍（在長方形邊界上的奶牛計為被包圍的）。請幫助Farmer John求出滿足他的要求的圍欄的最小可能周長。有可能出現這一圍欄寬為0或高為0的情況。

輸入樣例：

7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 6

輸出樣例：

10

供題：Brian Dean

翰林USACO課程體系流程圖