题目描述

Farmer John 的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通，这样，John 就有多个牧场了。

John 想在牧场里添加恰好一条路径。对这条路径有以下限制：

一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。

输入文件包括牧区、它们各自的坐标，还有一个对称邻接矩阵。其他邻接表中可能直接使用行列而不使用字母来表示每一个牧区。输入数据中不包括牧区的名字。

输入文件至少包括两个不连通的牧区。

请编程找出一条连接属于两个不同牧场的牧区的路径，使得连上这条路径后，这个更大的新牧场的直径尽可能小。输出在所有合法的连接方案中，新牧场直径的最小值。

输入格式

第一行一个整数 $N$，表示牧区数。

接下来 $N$ 行，每行两个整数 $X, Y$，表示 $N$ 个牧区的坐标。注意每个牧区的坐标都是不一样的。

接下来 $N$ 行，每行 $N$ 个数字，代表邻接矩阵 $M$。第 $i$ 行第 $j$ 列的数字为 $1$，表示 $i$ 号牧区和 $j$ 号牧区之间存在一条道路直接相连；为 $0$，表示不存在直接相连的道路。保证 $M_{i,j} = M_{j,i}$。

输出格式

只有一行，包括一个实数，表示所求直径。数字保留六位小数。

只需要打到小数点后六位即可，不要做任何特别的四舍五入处理。

样例

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

22.071068

数据范围

• $1 \le N \le 150$
• $0 \le X, Y \le 10^5$