Probability of Greedy Maximum Independent Set

In this problem, you are given an undirected graph with n vertices and m edges. A well‐known NP--complete problem is to find a maximum independent set. Although there is no known exact polynomial algorithm for this problem, many approximate algorithms with polynomial complexity exist. One common greedy algorithm is as follows:

1. For an undirected graph with n vertices, generate a random permutation p[1…n] of the vertices (each permutation is equally likely).
2. Initialize an answer set S as empty. Then, for i=1…n in order, if S \cup {p[i]} is still an independent set, add p[i] to S.
3. Output the independent set S.

Note that the set S produced by this algorithm is always a maximal independent set (i.e. no vertex can be added without breaking the independence).

Let \(\alpha\) be the size of a maximum independent set of the given graph. The greedy algorithm returns a maximum independent set if and only if \(|S|=\alpha\). Your task is to compute the probability that the algorithm yields a maximum independent set, modulo \(998244353\). More formally, if there are \(T\) permutations (out of \(n!\) total) that lead to the algorithm outputting an independent set of size \(\alpha\), then you should output \[ \frac{T}{n!} \mod 998244353, \] where division is defined modulo \(998244353\) (that is, compute \(T \times (n!)^{-1}\) modulo \(998244353\)).

Important: All formulas must be written in \(\LaTeX\) format. For example, the maximum independent set size is denoted by \(\alpha\) and the permutation is \(p[1\ldots n]\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq 10,\; 0 \leq m \leq \frac{n(n-1)}{2})\) representing the number of vertices and edges, respectively. The next \(m\) lines each contain two integers \(u\) and \(v\) \((1 \leq u,v \leq n,\; u \neq v)\) which denote an undirected edge between vertices \(u\) and \(v\). It is guaranteed that there are no duplicate edges.

outputFormat

Output a single integer, the probability (as defined above) modulo \(998244353\).

sample

3 0

1