Description

windy has a rectangular piece of land divided into $N\times M$ small $1\times 1$ cells. Some cells contain obstacles. If cell A can reach cell B, then the distance between them is defined as the Euclidean distance between their centers. If cell A cannot reach cell B, then there is no distance between them. If cells X and Y share a common edge and both X and Y contain no obstacles, you can move from X to Y. If windy can remove $T$ obstacles, find the maximum distance over all pairs of cells (considering only pairs where one can reach the other). It is guaranteed that after removing $T$ obstacles, at least one cell contains no obstacle.

Input Format

The first line contains three integers, $N,M,T$. Then there are $N$ lines, each containing a string of length $M$, where 0 denotes an empty cell and 1 denotes a cell containing an obstacle.

Output Format

Output a single floating-point number, with $6$ digits after the decimal point.

3 3 0
001
001
110

1.414214

4 3 0
001
001
011
000

3.605551

3 3 1
001
001
001

2.828427

Hint

• For $20\%$ of the testdata, $1 \le N,M \le 30$ and $0 \le T \le 0$.
• For $40\%$ of the testdata, $1 \le N,M \le 30$ and $0 \le T \le 2$.
• For $100\%$ of the testdata, $1 \le N,M \le 30$ and $0 \le T \le 30$.

Translated by ChatGPT 5