Moocast (Gold)#10562
Farmer John's cows want to organize an emergency "moo-cast" system for broadcasting important messages among themselves.
Instead of mooing to one another over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. Each walkie-talkie has a limited transmission range. However, cows can relay messages to one another along a path consisting of several hops, so it is not necessary for every cow to be able to communicate directly with every other cow.
The cows need to decide how much money to spend on their walkie-talkies. If they spend , each cow will receive a walkie-talkie capable of transmitting up to a distance of \sqrt{x}. In other words, two cows can communicate directly if and only if the squared distance between them is at most .
Please help the cows determine the minimum integer value of such that a broadcast originating from any cow can ultimately reach every other cow.
The first line contains number n~(1 \le n \le 1000). The next lines each contain the and coordinates of a single cow. Both coordinates are integers in the range .
Print one integer , the minimum amount the cows must spend on walkie-talkies.
Example 1