Fence Planning

题目描述

Farmer John 有 $N$ 头奶牛，方便起见编号为 $1 \ldots N$（$2 \leq N \leq 10^5$）。它们有着复杂的社会结构，围绕着“哞网络”（moo networks）——一些较小的牛群组展开：同一组内的奶牛可以相互交流，但不同组之间不能交流。 每头奶牛位于农场二维地图上一个不同的 $(x,y)$ 位置，并且我们知道有 $M$ 对奶牛（$1 \leq M < 10^5$）会互相“哞叫”。两头互相“哞叫”的奶牛属于同一个哞网络。 为了更新他的农场，Farmer John 想建造一个矩形栅栏，其边与 $x$ 轴和 $y$ 轴平行。Farmer John 想确保至少有一个哞网络被该栅栏完全包围（矩形边界上的奶牛也算被包围）。请帮助 Farmer John 确定满足该要求的栅栏的最小可能周长。这个栅栏允许宽度为 0 或高度为 0。

输入格式

第一行输入包含 $N$ 和 $M$。接下来 $N$ 行每行包含一头奶牛的 $x$ 和 $y$ 坐标（不超过 $10^8$ 的非负整数）。接下来 $M$ 行每行包含两个整数 $a$ 和 $b$，描述奶牛 $a$ 与奶牛 $b$ 之间的一条哞叫连接。每头奶牛至少有一条哞叫连接，且输入中不存在重复的连接。

输出格式

请输出满足 Farmer John 要求的栅栏的最小周长。

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|2019|Silver

来源

USACO|2019|Silver