UOJ Logo

NOI.AC

2S 512MB
统计

小w高考之后,为了和同学出去旅游,想要知道每个城市两两之间的最短距离。

小w生活的国家,是一个有$n$个城市的小国,城市之间有$m$条权值为$1$的无向边相连。

小y一眼就看出来这是一个经典的多最短路问题,不过因为小w并不是一个斤斤计较的人,他只想知道大致的距离。

如果两点间距离为$d$,那么输出$d$, $d + 1$或者$d + 2$,都算正确。

聪明的你能帮助小w规划他的旅行吗?

为了加速输出,小w只会询问$q$对点之间的距离。

输入格式

一行两个整数$n, q$。

之后$n$行,每行一个长度为$n$的01串。输入一个01矩阵。

$A_{i,j} = 1$表示$i$和$j$之前有边,$A_{i,j} = 0$表示$i$和$j$之间没有边。保证矩阵是对称的,$A_{i,j} = A_{j,i}$。

接下来$q$行,每行两个整数$a, b$,表示询问$a$和$b$之间的最短路径。

输出格式

$q$行,每行输出一个答案,只要在$[ans, ans + 2]$的区间内,就算正确。如果不连通,输出$998244353$。

样例一

input

5 5
11111
11111
11111
11111
11111
1 2
1 3
2 3
4 2
5 1

output

3
1
1
2
2

数据范围

时间限制2s, 空间限制512MB

测试点编号 $n$的规模 $q$的规模
1,2$n \leq 500$ $q \leq 10^5$
3,4,5,6$n \leq 2000$
7,8,9,10$n \leq 4000$