You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

本题大样例

给定一个包含 $n$ 个点 $m$ 条边的简单无向连通图（无自环、重边），点编号为 $1,2,\dots,n$。

给定一个非负整数 $k$，保证 $0\le k\le 2$。

你需要对于所有满足 $0\le i\le k$ 的非负整数 $i$ 求出，有多少种从 $m$ 条边中选出 $n-1+i$ 条边的方案，满足只保留 $n$ 个点和选出的这 $n-1+i$ 条边的图依然连通

由于答案可能很大，所以你只需要求出对 $998244353$ 取模后的结果。

输入描述

第一行三个整数 $n,m,k$。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示图上连接 $u_i,v_i$ 的一条无向边。

输出描述

共 $k+1$ 行，每行一个整数。

第 $i+1$ 行输出的整数表示有多少种从 $m$ 条边中选出 $n-1+i$ 条边的方案，满足只保留 $n$ 个点和选出的这 $n-1+i$ 条边的图依然连通，对 $998244353$ 取模后的结果。

样例输入

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

样例输出

16
15
6

对于 $100\%$ 的数据，$1\le n\le 17,n-1\le m\le\frac {n(n-1)}2,0\le k\le 2,1\le u_i,v_i\le n$，保证图连通，无自环、重边。