P5429 [USACO19OPEN] Fence Planning S

Farmer John has $N$ cows, numbered $1 \ldots N$ ($2 \leq N \leq 10^5$). They have a complex social network based on “moo-networks”: groups of cows that communicate with each other within the group but do not communicate with cows in other groups. Each cow is at a distinct position $(x, y)$ on a 2D map of the farm, and we know that there are $M$ pairs of cows ($1 \leq M < 10^5$) that moo to each other. Two cows that moo to each other belong to the same moo-network. To upgrade his farm, Farmer John wants to build a rectangular fence whose four sides are parallel to the $x$-axis and the $y$-axis. He wants at least one moo-network to be completely enclosed by the fence (cows on the boundary of the rectangle are considered enclosed). Please help Farmer John find the minimum possible perimeter of a fence that satisfies his requirement. It is possible that the fence has width $0$ or height $0$.

The first line contains $N$ and $M$. The next $N$ lines each contain the $x$ coordinate and $y$ coordinate of a cow (non-negative integers up to $10^8$). The next $M$ lines each contain two integers $a$ and $b$, indicating that cows $a$ and $b$ have a mooing relationship. Each cow has at least one mooing relationship, and there are no duplicate mooing relationships in the input.

Output the minimum perimeter of a fence that satisfies Farmer John’s requirement.

Translated by ChatGPT 5