题目描述

小婷照看着牧场中的 $N$ 头奶牛。第 $i$ 头奶牛位于平面坐标 $(x_i,y_i)$，每头奶牛都携带一台功率相同的无线电设备。

小婷需要为所有设备设定同一个整数功率 $X$。当奶牛 $i$ 与奶牛 $j$ 之间的欧氏距离平方不超过 $X$ 时，奶牛 $i$ 可以把消息直接发送给奶牛 $j$。一头奶牛收到消息后还可以继续转发，因此消息允许经过若干头奶牛中转。

小婷希望无论最初由哪一头奶牛发出消息，消息最终都能够到达其余所有奶牛。请计算能够满足这一要求的最小整数功率 $X$。

两点 $(x_i,y_i)$ 与 $(x_j,y_j)$ 之间的距离平方为 $(x_i-x_j)^2+(y_i-y_j)^2$。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，第 $i$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 头奶牛的位置。

输出格式

输出一个整数，表示使消息能够在所有奶牛之间传播的最小功率 $X$。

4
1 3
5 4
7 2
6 1

17

2
0 0
3 4

25

样例说明 #2

两头奶牛相距 $5$，距离平方为 $25$，因此最小功率为 $25$。

3
0 0
1 0
5 0

16

数据范围与约定

$1\le N\le1000$，$0\le x_i,y_i\le25000$。输入中的所有数均为整数。