У Фермера Джона \(N\) коров, последовательно пронумерованных d \(1 \ldots N\) (\(2 \leq N \leq 10^5\)).
Они организованы в сложную социальную структуру "moo networks" - маленькие группы коров
взаимодействуют внутри группы, но не с другими группами.
Каждая корова расположена в точке \((x,y)\) на двумерной карте фермы.
И нам известны \(M\) (\((1 \leq M < 10^5)\)) пар коров, принадлежащих к одной и той же группе.
ФД хочет построить прямоугольную изгородь со сторонами параллельными осям координат.
ФД хочет гарантировать, что как минимум одна группа коров целиком окажется внутри изгороди.
Коровы на границе, считаются принадлежащими прямоугольной изгороди.
Определите минимально возможный периметр такой изгороди. Допускается, что такая изгородь
может иметь нулевую ширину или высоту.
ФОРМАТ ВВОДА (файл fenceplan.in):
Первая строка ввода содержит \(N\) и \(M\). Каждая из следующих \(N\) строк содержит
\(x\) и \(y\) - координаты коров (неотрицательные целые числа не более \(10^8\)).
Каждая из следующих \(M\) строк содержит два целых числа \(a\) и \(b\), описывающих
принадлежность коров с номерами \(a\) и \(b\) к одной группе. Каждая корова присутствует
как минимум в одной из таких пар. Никакие пары во вводе не повторяются.
ФОРМАТ ВЫВОДА (файл fenceplan.out):
Выведите минимальный периметр, удовлетворяющий ограничениям ФД.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|