题目描述

你现在有 $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

大样例

link

数据范围

对于所有的数据，满足 $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$。