UOJ Logo

NOI.AC

2S 512MB
GoodBad[-13]
统计

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

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

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

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

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

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

输入格式

一行两个整数n,q

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

Ai,j=1表示ij之前有边,Ai,j=0表示ij之间没有边。保证矩阵是对称的,Ai,j=Aj,i

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

输出格式

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,2n500 q105
3,4,5,6n2000
7,8,9,10n4000