题目描述

给定一个无向图和一个正整数 $n$。记 $d(a,b)$ 为：

• 从顶点 $a$ 到顶点 $b$ 的最短路径长度（按边数计），如果两点连通；
• 若两点之间不存在路径，则 $d(a,b)=\infty$。

如果四元组 $(u_1,v_1,u_2,v_2)$ 同时满足以下条件，我们称其为一个有趣四元组：

1. $u_1,v_1,u_2,v_2$ 两两不同；
2. $d(u_1,v_1)=1$；
3. $d(u_2,v_2)=1$；
4. $d(u_1,u_2) \ne \infty$；
5. $d(v_1,v_2) \ne \infty$。

也就是说，$(u_1,v_1)$ 和 $(u_2,v_2)$ 都必须是图中的边，并且 $u_1,u_2$ 连通、$v_1,v_2$ 也连通。

请编写程序 graph，求出所有有趣四元组中

的最小可能值。

如果不存在有趣四元组，输出 $-1$。

输入格式

第一行输入一个整数 $n$，表示顶点数。

接下来共有 $n-1$ 行。

第 $i$ 行包含 $n-1-i$ 个字符 $x_{i,i+1},x_{i,i+2},\dots,x_{i,n}$：

• 若某个字符为 1，表示顶点 $i$ 与对应顶点之间有一条无向边；
• 若为 0，表示两点之间没有边。

输出格式

输出一个整数，表示最小可能值；若不存在满足条件的四元组，输出 $-1$。

数据范围

• $1 \le n \le 5000$

子任务

只有通过某个子任务中的全部测试点，才能获得该子任务的全部分数。

样例输入 #1

4
111
11
1

样例输出 #1

2