题目描述

未来发明时间机器后，学习历史变得更容易了：只要前往对应年份亲眼观察事件即可。教授使用时间机器研究 Berland 在“大道路变革”时期的道路系统。

这场变革持续了 $k$ 年。在这 $k$ 年中，Berland 的道路系统每年都会变化。国家有 $n$ 个城市，编号为 $1$ 到 $n$。每一年，城市之间由 $n-1$ 条双向道路连接，并且任意两座城市之间都有唯一简单路径。也就是说，每一年的道路系统都是一棵树。

每天，教授选择两个城市 $s$ 和 $f$，依次前往这 $k$ 年中的每一年，并在该年的道路系统中从 $s$ 走到 $f$，记录路径上的所有城市，包括 $s$ 和 $f$。之后他写下一个数字：在这 $k$ 次旅行中都被访问到的城市数量。

教授研究完所有城市对后，不幸丢失了所有记录。他只剩下这 $k$ 年的道路地图。

请你帮他恢复所有可能的城市对 $(s,f)$ 对应的记录数字。

输入格式

第一行包含两个整数 $n,k$，表示城市数和年份数。

接下来给出 $k$ 棵树的描述。每棵树包含 $n-1$ 行，每行两个整数 $a,b$，表示这两个城市之间有一条道路。

保证每一年给出的道路系统都是一棵树。

输出格式

输出 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个数表示教授选择 $s=i,f=j$ 时写下的数字。

数据范围

• $1 \le n,k \le 500$
• $1 \le a,b \le n$
• $a\ne b$

样例 1 输入

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

样例 1 输出

1 3 2 2
3 1 3 2
2 3 1 2
2 2 2 1

样例 2 输入

3 3
1 2
2 3
2 3
3 1
3 1
1 2

样例 2 输出

1 2 2
2 1 2
2 2 1

说明

第一个样例中有 4 个城市，教授研究 2 年。

若 $s=1,f=2$：

• 第一年路径访问城市 $1,2,3,4$；
• 第二年路径访问城市 $1,2,4$。

两次都访问到的城市为 $1,2,4$，数量为 $3$。

若 $s=3,f=1$：

• 第一年路径访问城市 $1,3$；
• 第二年路径访问城市 $1,3,4$。

两次都访问到的城市为 $1,3$，数量为 $2$。