小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表示i和j之前有边,Ai,j=0表示i和j之间没有边。保证矩阵是对称的,Ai,j=Aj,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≤500 | q≤105 |
3,4,5,6 | n≤2000 | |
7,8,9,10 | n≤4000 |