CSES - Aalto Competitive Programming 2024 - wk10 - Mon - 6G network
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Uolevi has been hired to design the telecommunication antennas for the new 6G network. There will be n masts numbered 1,2,\dots,n where the antennas will be placed. The i-th mast is located at coordinates (x_i, y_i). Uolevi's task is to find the minimum distance the antennas need to cover so that the masts form a connected network. That is, for each pair of antennas, there should be a path connecting them that jumps along the antennas and no jump is longer than the coverage distance.

Input

First line contains a single integer n. The i-th of next n following lines contains two integers x_i and y_i.

Output

Print the minimum distance the antennas need to cover. The answer is considered correct if the relative or absolute error does not exceed 10^{-6}.

Constraints

  • 1 \leq n \leq 1000
  • -10^5 \leq x_i, y_i \leq 10^5

Example 1

Input:

3
0 0
1 1
2 0

Output:

1.41421356237309504880

Example 2

Input:

10
1.8568923303 6.8853148851
7.1589123998 6.9450347477
2.4712739299 -2.3123658325
-4.0493078929 -8.8657404813
-4.5468741052 -0.4466977651
6.2433745330 -0.4004565695
-2.1443041341 6.7215753809
-3.2520767671 2.9634375315
-2.6351692527 9.1431030903
-7.1929844479 7.4017450254

Output:

8.43373300459665028398

Example 3

Input:

2
-100000 -100000
100000 100000

Output:

282842.71247461900972552939