题目描述

在一个小房间里有 $n$ 个人，每个人会若干种语言，共有 $k$ 种语言。所有人都是内向者，聊天会打扰他们看书。

如果一个人要把消息传给另一个人，可以直接交流，也可以通过若干中间人传递。相邻两人交流时，必须选择一种双方都会的语言。

但是一旦使用某种语言交流，房间里所有会这种语言的人都会听懂并被打扰。发送消息的人希望通过选择传递链，使被打扰的人数尽可能少。

请对每一对人 $(A,B)$，求从 $A$ 给 $B$ 传递消息时，最少会打扰多少人。

输入格式

第一行包含两个整数 $n,k$。

接下来 $n$ 行描述每个人会的语言。第 $i$ 行格式为：

ki ai,1 ai,2 ... ai,ki

其中 $k_i$ 是第 $i$ 个人会的语言数，后面是语言编号，按升序给出。

约束：

• $2\le n\le 300$；
• $1\le k\le 300$；
• $1\le k_i\le k$；
• $1\le a_{i,j}\le k$。

输出格式

输出 $n$ 行，每行 $n$ 个整数 $f_{i,j}$。

$f_{i,j}$ 表示从第 $i$ 个人向第 $j$ 个人传递消息时最少被打扰的人数。主对角线输出 0。若无法传递消息，输出 $-1$。

样例 1 输入

6 4
2 1 2
2 2 3
1 2
1 1
2 3 4
1 4

样例 1 输出

0 3 3 2 4 5
3 0 3 4 2 3
3 3 0 4 4 5
2 4 4 0 5 6
4 2 4 5 0 2
5 3 5 6 2 0

样例 2 输入

4 3
2 1 2
1 1
1 2
1 3

样例 2 输出

0 2 2 -1
2 0 3 -1
2 3 0 -1
-1 -1 -1 0