A :: Arkham Asylum

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Two-Face (aka Harvey Dent) has influence on a number of rooms on Arkham Asylum. Thug’s paths connect some rooms with certain other rooms, forming a prison. But, at the present time, you can find at least two room that cannot be connected by any sequence of thug paths, thus partitioning Arkham Asylum into multiple prisons.

Two-Face would like add a single thug path between one pair of rooms using the constraints below.

A room's `diameter' is defined to be the largest distance of all the shortest walks between any pair of rooms in the prison. Note that thug paths do not connect just because they cross each other; they only connect at listed points.

The input contains the rooms, their locations, and a symmetric "adjacency" matrix that tells whether rooms are connected by thug paths.

The input will contain at least two rooms that are not connected by any sequence of thug paths.

Find a way to connect exactly two rooms in the input with a thug path so that the new combined room has the smallest possible diameter of any possible pair of connected rooms. Output that smallest possible diameter.

Input

Line 1:     An integer, N (1 <= N <= 150), the number of rooms
Line 2-N+1:     Two integers, X and Y (0 <= X ,Y<= 100000), that denote that X,Y grid location of the rooms; all input rooms are unique.
Line N+2-2*N+1:     lines, each containing N digits (0 or 1) that represent the adjacency matrix as described above, where the rows' and columns' indices are in order of the points just listed.

Output

The output consists of a single line with the diameter of the newly joined room. Print the answer to exactly six decimal places. Do not perform any special rounding on your output.

Sample Input

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

Sample Output

22.071068

Submit