题目描述

湖面有 $n$ 个不同位置的木桩。小明从 1 号木桩出发，每次可跳到任意其他木桩，最终到达 $n$ 号木桩。求所有可行路线中，最长单次跳跃距离的最小值的平方。

输入格式

第一行一个正整数 $n$。接下来 $n$ 行，每行两个整数 $x_i,y_i$。

输出格式

输出一行一个整数，表示最优路线中最长单次跳跃距离的平方。

样例 1

4
0 0
1 1
3 1
4 0

4

数据范围

$2\le n\le5000$，$-10^5\le x_i,y_i\le10^5$，所有木桩坐标互不相同。

提示： 距离平方可以用整数运算计算，不需要浮点数。