\(N\) con bò của Farmer John, được đánh số thuận tiện từ \(1 \ldots N\) (\(2 \leq N \leq 10^5\)), có một cấu trúc xã hội phức tạp xoay quanh các "mạng lưới tiếng rống" — những nhóm bò nhỏ hơn giao tiếp trong nội bộ nhóm nhưng không giao tiếp với các nhóm khác.

Mỗi con bò ở một vị trí \((x,y)\) riêng biệt trên bản đồ 2D của trang trại, và ta biết có \(M\) cặp bò (\(1 \leq M < 10^5\)) rống với nhau. Hai con bò rống với nhau thuộc cùng một mạng lưới tiếng rống.

Trong nỗ lực nâng cấp trang trại, Farmer John muốn dựng một hàng rào hình chữ nhật có các cạnh song song với trục \(x\) và \(y\). Farmer John muốn đảm bảo rằng ít nhất một mạng lưới tiếng rống được hàng rào bao kín hoàn toàn (những con bò nằm trên biên hình chữ nhật cũng được tính là ở bên trong). Hãy giúp Farmer John xác định chu vi nhỏ nhất có thể của một hàng rào thỏa mãn yêu cầu này. Hàng rào có thể có chiều rộng bằng không hoặc chiều cao bằng không.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo chứa tọa độ \(x\) và \(y\) của một con bò (các số nguyên không âm không vượt quá \(10^8\)). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\), mô tả một liên kết rống giữa bò \(a\) và bò \(b\). Mỗi con bò có ít nhất một liên kết rống, và không có liên kết nào được lặp lại trong dữ liệu vào.

Dữ liệu ra

In ra chu vi nhỏ nhất của một hàng rào thỏa mãn các yêu cầu của Farmer John.

Ví dụ

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

Nguồn

USACO 2019 US Open Contest, Silver — Fence Planning

Tác giả: Brian Dean.