Farmer John's $N$ cows ($1 \leq N \leq 10^5$) are spread far apart on his farm
and would like to build a communication network so they can more easily exchange
electronic text messages (all of which of course contain variations of "moo").

The $i$th cow is located at a distinct location $(x_i,y_i)$ where
$0 \leq x_i \leq 10^6$ and $0 \leq y_i \leq 10$. The cost of building a
communication link between cows $i$ and $j$ is the squared distance between
them: $(x_i-x_j)^2 + (y_i-y_j)^2$.

Please calculate the minimum cost required to build a communication network
across which all the cows can communicate. Two cows can communicate if they are
directly connected by a link, or if there is a sequence of links along which
their message can travel.

Note: the time limit for this problem is 4s, twice the default.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains $N$, and the next $N$ lines each describe the
$x$ and $y$ coordinates of a cow, all integers.

OUTPUT FORMAT (print output to the terminal / stdout):
Please output the minimum cost of a network that will allow all cows to
communicate. Note that this cost might be too large to fit into a 32-bit
integer and may require use of 64-bit integers (e.g., "long long" integers in
C++).

SAMPLE INPUT:
10
83 10
77 2
93 4
86 6
49 1
62 7
90 3
63 4
40 10
72 0
SAMPLE OUTPUT:
660

SCORING:
Test cases 2-3 satisfy $N \le 1000$.Test cases 4-15 satisfy no additional constraints.

Problem credits: Brian Dean

见题面

见题面