A75432.[GESP202503 七级] 图上移动

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

第一行,三个正整数 n , m , k ,分别表示无向图的结点数与边数,最多移动的步数｡
接下来 m 行,每行两个正整数 $u_i$ , $v_i$ ,表示图中的一条连接结点$u_i$ 与 $v_i$ 的无向边｡

共 n 行,第 i行(1 ≤i ≤n)包含 k 个整数,第 j 个整数( 1 ≤j ≤k )表示从结点 出发恰好移动 j 步之后可能位 于的结点数量｡

对于 20% 的测试点,保证 k = 1
对于另外 20% 的测试点,保证 1 ≤n ≤50 , 1 ≤m ≤50。
对于所有测试点,保证 1 ≤n ≤500, 1 ≤m ≤500 , 1 ≤k ≤20 , $1 ≤u_{i}, v_{i} ≤n$