题目描述

定义一个无向图 $G$ 的线图 $\text{line graph}$ 变换为：对于点集 $V$ ，边集 $E$ 的无向图 $G$ ，该图的线图 $L(G)$ 也是一个无向图：

1. $L(G)$ 的点集大小为 $|E|$ ，每个点唯一对应着原图的一条边。
2. 两个点之间有边当且仅当这两个点对应的边在原图上有公共点（注意不会存在自环）。

比较容易注意到，无向图 $G$ 经过若干轮线图变换后，其点数和边数可能会呈指数级别的增长。

给定一个无向图 $G$ ，询问该线图 $L^k (G)$ 的最大独立集大小，答案对 $998244353$ 取模即可。

输入格式

输入的第一行包含两个正整数 $n,m$ 表示该无向图的点数和边数。

接下来 $m$ 行，每行两个正整数 $u,v$ 表示原图的一条边 $(u,v)$ 。

输出格式

输出一行一个整数，表示答案。

数据范围

本题开启子任务评测。对于全部数据，保证 $1 \leq n,m \leq 2000$ ，$2 \leq k \leq 7$ 。

子任务 1（ $10$ 分 ）：$k=2$ 。

子任务 2（ $10$ 分 ）：$k=3$ 。

子任务 3（ $20$ 分 ）：$k=4$ 。

子任务 4（ $20$ 分 ）：$k=5$ 。

子任务 5（ $20$ 分 ）：$k=6$ 。

子任务 6（ $20$ 分 ）：$k=7$ 。

样例输入

5 4 3
1 2
2 3
2 5
3 4

样例输出

2