题目描述
你现在有 $n$个长度为 $m$ 的字符串 $S_1,\dots,S_n$ ,满足字符集为 ${1,2,\dots,n}$。你还有一个长度为 ¥吗¥ 的模式字符串 $T$,模式串的每个位置上除了 ${1,2,\dots,n}$ 之外还可以有一个通配符 $0$。
现在,$n$ 个字符串排成了一个环,对于 $S_i$,它右边的字符串为 $S_{(i \ \bmod \ 1)+1}$;而对于 $S_{(i \ \bmod \ 1)+1}$,它左边的字符串 $S_i$。
现在,我们在串 $S_a$ 处,然后我们希望能达到串 $S_b$。初始的时候,$T$ 的每一位都是 $0$。每一回合,加入当前处于 $S_x$,你可以进行如下的操作之一:
- (操作一)从 $S_x$ 的右边的串开始,不断向右移动,直到移动到了 $S_y$ 使得 $T$ 与 $S_y$ 匹配。
- (操作二)从 $S_x$ 的左边的串开始,不断向左移动,直到移动到了 $S_y$ 使得 $T$ 与 $S_y$ 匹配。
- (操作三)将 $T$ 任意一个字符为 $0$ 的位置更改为 ${1,2,\dots,n}$ 中的任意一个数。更改完毕后,如果 $T$ 仍然能匹配 $S_x$,那么次回合中不移动;否则会不断向右移动,直到移动到了 $S_y$ 使得 $T$ 与 $S_y$ 匹配。注意,如果不存在 $y$ 使得 $S_y$ 与 $T$ 匹配,那么这回合的操作是非法的,会直接死机。
- (操作四)将 $T$ 任意一个字符非 $0$ 的位置更改为 $0$,不移动。
请你对于所有的 $a,b$,都求出:如果初始在 $S_a$ 处,在满足所有回合操作都合法的情况下,最少需要多少个回合可以到达 $S_b$。
输入格式
第一行两个正整数 $n,m$
后面 $n$ 行,每行 $m$ 个正整数,描述一个字符串。
输出格式
$n$ 行,每行 $n$ 个整数。第 $i$ 行的第 $j$ 个正整数表示 $a=i,b=j$ 时的答案。
样例输入 1
4 1
4
2
3
2
样例输出 1
0 1 1 1
1 0 1 2
1 1 0 1
1 2 1 0
样例解释 1
$a=1,b=2$ 时,进行一次操作一即可;$a=1,b=3$ 时,进行一次操作三,操作三中将 $T$ 的唯一一位从 $0$ 更改成 $3$ 后会直接移动到 $S_3$。$a=2,b=4$ 时,若第一步就进行操作三把 $T$ 更改为 $2$ 的话就还会待在原地;而问你应该直接做两次操作一来得到最优解。
样例输入 2
6 3
1 3 2
2 1 1
2 1 2
1 3 3
1 3 2
2 3 2
样例输出 2
0 1 2 1 2 1
1 0 1 1 2 2
2 1 0 1 2 2
2 1 1 0 1 1
2 1 2 1 0 1
1 1 2 1 1 0
大样例
数据范围
对于所有的数据,满足 $2\leq n \leq 500$,$1 \leq m \leq 5$
$\text{Subtask 1(10 pts)}$ $m \leq 1$,$n \leq 50$。
$\text{Subtask 2(10 pts)}$ $m \leq 2$,$n \leq 150$。
$\text{Subtask 3(10 pts)}$ $m \leq 3$,$n \leq 250$。
$\text{Subtask 4(10 pts)}$ $m \leq 4$,$n \leq 350$。
$\text{Subtask 5(10 pts)}$ $m \leq 5$,$n \leq 300$。
$\text{Subtask 6(10 pts)}$ $m \leq 5$,$n \leq 500$。