题目描述

农场有 $N$ 个牧区，每个牧区有一个平面坐标。一些牧区之间有双向道路，道路长度等于两端点的直线距离。互相连通的牧区构成一个牧场；牧场的直径是其中任意两个牧区之间最短距离的最大值。

你需要恰好添加一条道路，连接原本属于不同牧场的两个牧区，使添加后所有牧场中最大的直径尽可能小。道路在中途相交不代表可以换路，只有共同端点才表示相连。输入保证至少有两个牧场。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $X_i,Y_i$。

接下来 $N$ 行，每行一个长度为 $N$ 的 01 字符串，表示对称邻接矩阵。字符为 1 表示两点之间有道路，否则没有道路。对角线为 0。

输出格式

输出最小的直径，保留六位小数。

样例

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

数据范围

$2\le N\le150$，$0\le X_i,Y_i\le100000$。任意两个牧区的坐标不同。