Moocast

Interview

Time limit2sMemory limit512 MB

Summary

Given N cow coordinates, find the smallest integer X such that the graph connecting pairs whose squared distance is at most X is connected.

Level: Medium5 of 10
Topics: Graph, Union-find, Sorting, Minimum spanning tree
Solved: No attempts yet

Problem

Farmer John's N cows (1 ≤ N ≤ 1000) want to build an emergency broadcast system for passing important messages among themselves.

Instead of mooing at each other over long distances, the cows decide to carry one walkie-talkie each. Every walkie-talkie has a limited transmission radius, but the cows can relay a message along a path of several hops. So not every cow has to transmit directly to every other cow.

The cows now have to decide how much money to spend on the walkie-talkies. If they spend $X, each cow gets a walkie-talkie that transmits up to a distance of $\sqrt{X}$ . That is, the squared distance between two cows must be at most X for them to communicate directly.

Find the minimum integer value of X such that a broadcast from any cow eventually reaches every other cow.

Input

The first line contains N.

Each of the next N lines contains the x and y coordinates of one cow. Both are integers between 0 and 25,000.

Output

Print a single line containing the integer X, the minimum amount the cows must spend on walkie-talkies.

Examples2

Example 1
Input
```
4
1 3
5 4
7 2
6 1
```
Expected output
```
17
```
Example 2
Input
```
5
0 0
1 0
1 3
5 3
5 0
```
Expected output
```
16
```