图上移动

题目描述

⼩ A 有⼀张包含 个结点与 条边的⽆向图，结点以 标号。⼩ A 会从图上选择⼀个结点作为起点，每⼀ 步移动到某个与当前⼩ A 所在结点相邻的结点。对于每个结点 （ ），⼩ A 想知道从结点 出发恰好移动 步之后，⼩ A 可能位于哪些结点。由于满⾜条件的结点可能有很多，你只需要求出这些结点的数量。

输入格式

第⼀⾏，三个正整数 ，分别表⽰⽆向图的结点数与边数，最多移动的步数。 接下来 ⾏，每⾏两个正整数 ，表⽰图中的⼀条连接结点 与 的⽆向边。

输出格式

共 ⾏，第 ⾏（ ）包含 个整数，第 个整数（ ）表⽰从结点 出发恰好移动 步之后可能位 于的结点数量。

样例输入 #1

4 4 3
1 2
1 3
2 3
3 4

样例输出 #1

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

数据范围

对于 % 的测试点，保证 。 对于另外 % 的测试点，保证 ， 。 对于所有测试点，保证 ， ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。