图上移动

题目描述

小 A 有一张包含 n 个结点与 m 条边的无向图，结点以 1..n 标号。小 A 会从某个结点出发，每一步移动到某个相邻结点。对于每个结点 i，问从结点 i 出发恰好移动 t 步 (1 ≤ t ≤ k) 之后，可能位于的结点数量。

输入格式

第一行三个正整数 n, m, k；接下来 m 行，每行两个正整数 u, v，表示一条无向边。

输出格式

共 n 行，第 i 行含 k 个整数，第 t 个整数表示从结点 i 出发恰好 t 步后可能位于的结点数量。

样例

输入：4 4 3\n1 2\n1 3\n2 3\n3 4\n输出：\n2 4 4\n2 4 4\n3 3 4\n1 3 3

数据范围

对于所有测试点，保证 1 ≤ n ≤ 500，1 ≤ m ≤ 505，1 ≤ k ≤ 24。