#G1104. [GESP202503 七级] 图上移动
[GESP202503 七级] 图上移动
[GESP202503 七级] 图上移动
题目描述
小 A 有一张包含 个结点与 条边的无向图,结点以 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 (),小 A 想知道从结点 出发恰好移动 步之后,小 A 可能位于哪些结点。由于满足条件的结点可能有很多,你只需要求出这些结点的数量。
输入格式
第一行,三个正整数 ,分别表示无向图的结点数与边数,最多移动的步数。
接下来 行,每行两个正整数 ,表示图中的一条连接结点 与 的无向边。
输出格式
共 行,第 行()包含 个整数,第 个整数()表示从结点 出发恰好移动 步之后可能位于的结点数量。
样例 #1
样例输入 #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
数据范围
| 测试点 | 数据范围 | 说明 |
|---|---|---|
| 1~2 | 无 | |
| 3~4 | , | |
| 全部 | ,,, |