在未来时光机器被发明出来了。Dr. D 打算对HY的交通系统进行研究。研究将跨越k个时间，每个时间虽然地点没变，但道路改变了。HY的交通系统中，有$n$个地点，这些地点被$n-1$条道路所联通。任意一对地点之间有且仅有一条路。

Dr.D选择两个城市$s$和$f$，从$s$旅行到$f$，访问路上的所有城市，包括$s$和$f$。在$k$个时间访问之后，他会写下这$k$次旅行中每次都能访问的城市有多少，换句话说，把每次访问的城市当成一个集合，他会写下这$k$个集合的交集大小。

很不幸的是完成工作后Dr.D弄丢了他的笔记本。他现在只有这k个时间的交通系统的图。Dr.D想知道对于所有可能的$s$和$f$，对应的记录应该是多少。

输入格式

第一行包含两个数$n$和$k$。分别是地点数和时间数。$(1 \leq n,k \leq 500)$

接下来是对道路系统的$k$个描述。

每个描述由n-1行组成，每行一对$a,b$，代表这条道路连接的城市。$(1 \leq a,b \leq n, a \neq b)$

保证每个交通系统对于任意两个地点之间有且仅有一条路。

输出格式

一个$n \times n$ 的矩阵，第i行的第j个数字表示$s=i,f=j$。

输入样例

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

样例输出

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