#Pslive1. Fence Planning

    ID: 608 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>sliver赛制:ACM来源:wyfoj http://127.0.0.1并查集

Fence Planning

Fence Planning

题目描述

Farmer John的N头奶牛,编号为1…N(2≤N≤10510^5),拥有一种围绕“哞网”,一些仅在组内互相交流却不与其他组进行交流的奶牛小组,组成的复杂的社交网络。

每头奶牛位于农场的二维地图上的不同位置(x,y),并且我们知道有M对奶牛(1≤M<10510^5)会相互哞叫。两头相互哞叫的奶牛属于同一哞网。

为了升级他的农场,Farmer John想要建造一个四边与x轴和y轴平行的长方形围栏。Farmer John想要使得至少一个哞网完全被围栏所包围(在长方形边界上的奶牛计为被包围的)。请帮助Farmer John求出满足他的要求的围栏的最小可能周长。有可能出现这一围栏宽为0或高为0的情况。

输入格式

输入的第一行包含N和M。以下N行每行包含一头奶牛的x坐标和y坐标(至多10810^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