题目描述

小A有一张包含 n 个结点与 m 条边的无向图，结点编号为 1 到 n。小A从某个结点出发，每一步移动到相邻结点。对于每个结点 i，计算从 i 出发恰好移动 1 到 k 步后可能位于的结点数量。

输入格式

• 第一行：n（结点数），m（边数），k（最大步数）
• 接下来 m 行：每行两个整数 u_i 和 v_i，表示一条无向边

输出格式

• 共 n 行，第 i 行包含 k 个整数，表示从结点 i 出发移动 1 到 k 步后的可达结点数

样例

输入

4 4 3
1 2
1 3
2 3
3 4

输出

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

数据范围

• 20% 数据：k = 1
• 20% 数据：1 ≤ n ≤ 50，1 ≤ m ≤ 50
• 100% 数据：1 ≤ n ≤ 500，1 ≤ m ≤ 500，1 ≤ k ≤ 20

题目来源

2025年3月GESP 7级