Description

There was once a "Duliu" (pinyin).

Duliu recently discovered the secret to mass-producing "duliu" problems. Consider a data-structure problem of the following type: given an array, you need to support several quirky update operations (for example, adding a number to a range, or taking the square root on a range), and support querying range sums. Duliu considered $n$ such update operations, numbered $1\sim n$. When Duliu wants to set a data-structure problem, he selects some of these update operations and turns them into a problem.

Of course, such a problem might be unsolvable. Through clever mathematical reasoning, Duliu revealed the relationships among these update operations: there are $m$ pairs of mutually exclusive update operations, and the $i$-th pair is the $u_i$-th operation and the $v_i$-th operation. When a problem contains both $u_i$ and $v_i$, the problem becomes unsolvable. On the other hand, if a problem contains no mutually exclusive pairs, then the problem is solvable. In addition, Duliu discovered a pattern: $m-n$ is a small number, and any two update operations are connected. Two update operations $a, b$ are connected if and only if there exist operations $t_0, t_1, \cdots, t_l$ such that $t_0 = a$, $t_l = b$, and for $1 \le i \le l$, $t_{i-1}$ and $t_i$ are mutually exclusive.

A pair of mutually exclusive update operations is called an exclusive pair. Now Duliu wants to know, given $n$ and the $m$ exclusive pairs, how many different solvable data-structure problems he can set. Two data-structure problems are different if and only if there exists an update operation that appears in one but not in the other.

Input Format

The first line contains positive integers $n, m$.

The next $m$ lines each contain two positive integers $u, v$, representing a pair of mutually exclusive update operations.

Output Format

Output a single integer on one line, representing the number of solvable different data-structure problems that Duliu can set. This number can be large, so output it modulo $998244353$.

3 2
1 2
2 3

5

6 8
1 2
1 3
1 4
2 4
3 5
4 5
4 6
1 6

16

12 18
12 6
3 11
8 6
2 9
10 4
1 8
6 2
11 5
10 6
12 2
9 3
7 6
2 7
3 2
7 3
5 6
2 11
12 1

248

Hint

Explanation for Sample 1

The solvable problems include $\varnothing, \{1\}, \{2\}, \{3\}, \{1, 3\}$. Note that the empty set is a valid data-structure problem.

Constraints

Translated by ChatGPT 5