题目描述

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

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

为了升级他的农场，Farmer John想要建造一个四边与 x 轴和 y 轴平行的长方形围栏。Farmer John想要使得至少一个哞网完全被围栏所包围（在长方形边界上的奶牛计为被包围的）。

请帮助Farmer John求出满足他的要求的围栏的最小可能周长。有可能出现这一围栏宽为0或高为0的情况。

输入格式

输入的第一行包含 N 和 M。以下 N 行每行包含一头奶牛的 x 坐标和 y 坐标。

以下 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

2 1
0 0
10 0
1 2

20

21 31
32744293 858
32744293 859
32744293 860
32744293 861
32744293 862
32744293 863
32744293 864
32744293 865
32744293 866
95520772 14220463
12366180 98915232
13893097 18769635
86789922 51472381
53240815 78397410
80026120 22997926
39484849 66921280
66220558 73169393
44752706 2974247
24638834 89737002
44846552 6623288
85338924 93941407
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
14 20
1 20
2 14
10 15
13 17
4 10
4 17
5 12
3 16
5 20
6 21
7 15

364137932

数据范围

$2\le N\le 10^{5}$，$1\le M\lt 10^{5}$，横纵坐标均为不超过$10^{8}$的非负整数。