Counting Subset Pairs on Graph Paths

You are given a simple, undirected, connected graph with n vertices and m edges. The vertices are numbered from \(1\) to \(n\). The graph has no self‐loops or multiple edges.

You are asked to count the number of ordered pairs of subsets \(S, T \subseteq \{1,2,\dots,n\}\) that satisfy the following condition:

For every vertex \(i \in S\), either \(i \in T\) or there exist two distinct vertices \(x, y \in T\) such that there exists a simple path from \(x\) to \(y\) that passes through \(i\) (i.e. \(i\) appears as an internal vertex of the path). Note that both \(S\) and \(T\) are allowed to be empty.

Output the answer modulo \(998244353\).

Note: A simple path is a path that does not repeat vertices. When we say that a path passes through \(i\), we mean that \(i\) is neither the start nor the end of the path but appears somewhere in between.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq 15,\ n-1 \leq m \leq \frac{n(n-1)}{2})\) — the number of vertices and the number of edges. It is guaranteed that the given graph is simple and connected.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) \((1 \leq u,v \leq n, u \neq v)\) indicating that there is an edge between vertices \(u\) and \(v\).

outputFormat

Output a single integer: the number of valid pairs \((S, T)\) modulo \(998244353\).

sample

3 2
1 2
2 3

31