Reachable Vertices Count

Given an undirected graph with $n$ vertices and $m$ edges (vertices are numbered $1,2,\dots,n$), you need to answer the following: For each vertex $i$ ($1\le i\le n$), if you start at vertex $i$ and move exactly $j$ steps (where $1\le j\le k$) with each move going to any adjacent vertex, compute the number of distinct vertices you can reach. Formally, let $\mathcal{S}(i, j)$ be the set of vertices that can be reached from vertex $i$ in exactly $j$ moves. You only need to output the size of $\mathcal{S}(i, j)$ for each vertex $i$ and each step count $j$.

inputFormat

The input begins with a single line containing three integers $n$, $m$, and $k$, where:

• $n$ is the number of vertices,
• $m$ is the number of edges, and
• $k$ is the maximum number of moves to simulate.

Each of the following $m$ lines contains two integers $u$ and $v$, representing an undirected edge connecting vertices $u$ and $v$.

outputFormat

Output $n$ lines. The $i$-th line must contain $k$ integers separated by spaces, where the $j$-th integer is the number of distinct vertices that can be reached from vertex $i$ in exactly $j$ moves.

sample

3 2 2
1 2
2 3

1 2
2 1
1 2

</p>