题目内容

春节将近，小塔想在节日期间逛一逛城里的 $N$ 个著名景点，正好所有的景点都能通过坐公交到达，请帮小塔设计一下，怎么搭乘公交路线才能最快逛完所有的景点。

1、景点编号 $0,1,2,…,N-1$

2、用数组 $arr[N] [N]$表示景点和景点之间是否有直达公交路线相连

3、$arr[i] [j]=1$ 表示景点 $i$ 和景点 $j$ 之间有直达公交相连，$arr[i] [j] =0$ 表示没有

4、公交可以双向行驶，即如果 $arr[i] [j]=1$，则必然 $arr[i] [j]=1$

5、每个景点可以经过多次，两个景点的公交也可以坐多次

6、可以从任一景点开始游玩

输入描述

第一行:景点数量 $N(0<N<=20)$

后续 $N$ 行: $N$ 个元素表示景点与景点之间的公交到达关系

输出描述

最少乘坐公交的次数(如果不能逛完所有景点，则输出 $0$ )

样例1

输入

5
0 1 0 1 0
1 0 1 0 0
0 1 0 0 0
1 0 0 0 1
0 0 0 1 0

输出

4

说明

样例2

输入

6
0 1 1 0 0 0
1 0 0 0 0 0
1 0 0 1 1 0
0 0 1 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0

输出

6

说明