图上移动
题目描述
小 A 有一张包含n 个结点与 m条边的无向图,结点以1,2,...,n 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 i(1≤i≤n ),小 A 想知道从结点i 出发恰好移动1,2,...,k步之后,小 A 可能位于哪些结点。由于满足条件的结点可能有很多,你只需要求出这些结点的数量。
输入格式
第一行,三个正整数 n,m,k,分别表示无向图的结点数与边数,最多移动的步数。
接下来m 行,每行两个正整数 ui,vi,表示图中的一条连接结点 ui与vi 的无向边。
输出格式
共n 行,第 i行(1≤i≤n )包含 k个整数,第j 个整数(1≤j≤k )表示从结点 i出发恰好移动j 步之后可能位于的结点数量。
输入样例
输出样例
数据范围
对于20 % 的测试点,保证k=1 。
对于另外20 % 的测试点,保证 1≤n≤50,1≤m≤50 。
对于所有测试点,保证 1≤n≤500,1≤m≤500 ,1≤k≤20 ,1≤ui,vi≤n。