타임 트래블

타임머신이 발명된 미래에는 역사를 배우기가 더 쉬워졌다. 이제는 해당 연도로 가서 사건을 직접 눈으로 볼 수 있다. 교수는 이 장치를 이용해 대전환 시기의 베를란드 도로망을 연구한다.

대전환은 연속된 $k$년 동안 진행되었다. 이 기간 동안 베를란드의 도로망은 계속 바뀌었다. 나라에는 $1$부터 $n$까지 번호가 매겨진 $n$개의 도시가 있다. 매년 이 도시들은 양방향 도로 $n-1$개로 연결되어 있으며, 어떤 두 도시 사이에도 경로는 하나뿐이다.

교수는 매일 두 도시 $s$와 $f$를 고른 뒤, 대전환의 각 연도를 차례로 거친다. 각 연도마다 $s$에서 $f$까지 이동하며, 경로에 있는 모든 도로를 지나간다. 이때 $s$와 $f$도 방문한 도시에 포함된다. 그다음 $k$번의 이동에서 모두 방문한 도시의 수를 기록한다.

안타깝게도 교수는 모든 도시 쌍을 조사한 뒤 기록을 모두 잃어버렸다. 남은 것은 대전환 $k$년 각각의 베를란드 도로망 지도뿐이다.

교수가 가능한 모든 도시 쌍 $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$줄에 걸쳐 각 줄마다 정수 $n$개를 출력한다. $i$번째 줄의 $j$번째 수는 $s=i$, $f=j$일 때 교수가 기록한 수이다.

첫 번째 예제 테스트에서 베를란드에는 도시가 $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$를 기록한다.