Minimum Maximum Communication Distance

You are given the coordinates of n towers on a plane. Two towers can directly communicate if the Euclidean distance between them is at most D. We wish to choose the smallest D such that, by connecting towers whose pairwise distance is at most D, all towers become connected (directly or indirectly).

This is equivalent to finding the minimum value of the maximum edge in a spanning tree connecting all towers. Formally, if the towers are located at coordinates \((x_i, y_i)\), then the Euclidean distance between tower \(i\) and tower \(j\) is given by \[ d(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}, \] find the minimum possible value of \(D\) such that there exists a spanning tree of the towers whose most expensive (longest) edge is at most \(D\).

Note: In the final output, print the integer part of the minimum required distance, i.e. use the built-in conversion to an integer (which truncates the decimal part).

inputFormat

The first line contains an integer n (\(2 \leq n \leq 10^5\)) denoting the number of towers. Each of the next n lines contains two integers, x and y (\(|x|,|y| \leq 10^9\)), representing the coordinates of a tower.

outputFormat

Output a single integer which is the minimum maximum communication distance required so that the network of towers is connected.

4
0 0
0 2
2 0
2 2

2