Farmer John đã đặt $N$ kiện cỏ khô, $(1 \le N \le 50,000)$, ở giữa một cánh đồng. Nếu xem đồng là lưới gồm $1,000,000$ $x$ $1,000,000$ ô vuông kích thước $1$ $x$ $1$, mỗi kiện chiếm đúng một ô (dĩ nhiên không có hai kiện chiếm cùng một ô).

FJ nhận thấy tất cả các kiện tạo thành một vùng liên thông lớn: từ bất kỳ kiện nào, có thể đến bất kỳ kiện khác bằng một chuỗi bước sang kiện kề trực tiếp ở phía bắc, nam, đông hoặc tây. Tuy nhiên, vùng liên thông có thể chứa “lỗ”, tức những vùng trống bị các kiện bao quanh hoàn toàn.

Hãy giúp FJ xác định chu vi vùng do các kiện tạo thành. Lưu ý rằng các lỗ không đóng góp vào chu vi.

Dữ liệu vào

• Dòng 1: số kiện cỏ khô, $N$.

• $N$ dòng tiếp theo, tức các dòng $2\ldots1+N$: mỗi dòng chứa vị trí ($x$, $y$) của một kiện, trong đó $x$ và $y$ đều là số nguyên trong khoảng $1\ldots1,000,000$. Vị trí $(1,1)$ là ô dưới cùng bên trái của đồng, và $(1000000,1000000)$ là ô trên cùng bên phải.

Dữ liệu ra

• Dòng 1: chu vi vùng liên thông của các kiện cỏ khô.

Ví dụ

Dữ liệu vào 1

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

Dữ liệu ra 1

14

Ghi chú

Vùng liên thông gồm các kiện có dạng sau:

XX 
X XX
XXX

Chu vi vùng liên thông là $14$ (chẳng hạn, cạnh trái đóng góp độ dài $3$ vào tổng). Lỗ ở giữa không đóng góp vào số này.

Tác giả bài toán: Brian Dean, 2013