Time Travel

In the future, after the time machine was invented, it became easier to learn history. Now you can just go to the corresponding year and watch the events yourself. A professor uses this device to study the system of Berland roads during the Great Road Transformation.

The transformation took $k$ consecutive years. During these years the system of roads of Berland changed. There are $n$ cities in the country, numbered from $1$ to $n$. Each year these cities were connected by $n-1$ bidirectional roads, so that for every pair of cities there was a unique path between them.

Every day the professor chooses two cities $s$ and $f$, then travels through every year of the Great Road Transformation, one after another. In each year he makes a trip from $s$ to $f$, visiting all roads on the path, including $s$ and $f$. After that he writes down the number of cities that were visited on all of his $k$ trips.

Unfortunately, after he finished his work and studied all pairs of cities, he lost all of his records. He only has maps of the Berland road system for all $k$ years of the Great Road Transformation.

Help the professor restore the numbers that he had written down for all possible pairs of cities $s$ and $f$.

The first line contains two integers $n$ and $k$, the number of cities in Berland and the number of years of the Great Road Transformation ($1 \leq n, k \leq 500$).

Then $k$ descriptions of the road systems follow, one for each year. Each description has $n-1$ lines, and each line contains two integers $a$ and $b$, the cities connected by a road ($1 \leq a, b \leq n$, $a \neq b$). It is guaranteed that for each of the $k$ years, every pair of cities has a unique path between them.

Output $n$ lines with $n$ integers in each. The $j$-th number in the $i$-th line must be the number the professor wrote down if $s=i$ and $f=j$.

There are $4$ cities in Berland in the first sample test. There are $2$ years studied by the professor. The map of the road system for the first year is shown on the left, and the map for the second year is shown on the right.

Consider the pair $s = 1$ and $f = 2$. In the first year, the professor visits cities $1$, $2$, $3$, $4$ on his trip. In the second year, he visits cities $1$, $2$, $4$. Cities $1$, $2$, $4$ are visited on all of his trips, so he writes down the number $3$ for this pair.

Consider the pair $s = 3$ and $f = 1$. In the first year, the trip visits cities $1$, $3$. In the second year, it visits cities $1$, $3$, $4$. Cities $1$ and $3$ are visited on all trips, so he writes down $2$ for this pair.