#G1104. [GESP202503 七级] 图上移动

[GESP202503 七级] 图上移动

[GESP202503 七级] 图上移动

题目描述

小 A 有一张包含 nn 个结点与 mm 条边的无向图,结点以 1,2,…,n1,2,\dots,n 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 ii(1≤i≤n1 \le i \le n),小 A 想知道从结点 ii 出发恰好移动 1,2,…,k1,2,\dots,k 步之后,小 A 可能位于哪些结点。由于满足条件的结点可能有很多,你只需要求出这些结点的数量。

输入格式

第一行,三个正整数 n,m,kn,m,k,分别表示无向图的结点数与边数,最多移动的步数。

接下来 mm 行,每行两个正整数 ui,viu_i,v_i,表示图中的一条连接结点 uiu_i 与 viv_i 的无向边。

输出格式

共 nn 行,第 ii 行(1≤i≤n1 \le i \le n)包含 kk 个整数,第 jj 个整数(1≤j≤k1 \le j \le k)表示从结点 ii 出发恰好移动 jj 步之后可能位于的结点数量。

样例 #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 k=1k=1 无
3~4 1≤n≤501 \le n \le 50,1≤m≤501 \le m \le 50
全部 1≤n≤5001 \le n \le 500,1≤m≤5001 \le m \le 500,1≤k≤201 \le k \le 20,1≤ui,vi≤n1 \le u_i,v_i \le n