\(S_k\) を \(A_k\) 人目と \(B_k\) 人目が隣り合うような並べ方全てからなる集合とします。求める値は \(\displaystyle \left|\bigcap_{i=1}^N \bar{S_i} \right|\) です。

包除原理より \(\displaystyle \left|\bigcap_{i=1}^N \bar{S_i} \right| = \sum_{T\subset \lbrace 1,2,\ldots,N \rbrace} (-1)^{|T|} \left| \bigcap_{i \in T} S_i \right| \) が成り立つので、各 \(\lbrace 1,2,\ldots,N \rbrace\) の部分集合 \(T\) に対して \(\displaystyle \left| \bigcap_{i \in T} S_i \right|\) が求まれば良いです。

\(N\) 頂点 \(|T|\) 辺のグラフ \(G\) を \(i \in T\) に対し頂点 \(A_{i}\) と頂点 \(B_i\) が辺で繋がれているようなグラフとします。すると、 \(\displaystyle \left| \bigcap_{i \in T} S_i \right|\) は以下のように求めることができます。

• \(G\) の連結成分であってパスグラフではないようなものが存在する場合、\(\displaystyle \left| \bigcap_{i \in T} S_i \right|=0\) 。
• \(G\) の連結成分が全てパスグラフである場合、連結成分数を \(X\) 、頂点数が \(2\) 以上の連結成分数を \(Y\) として \(\displaystyle \left| \bigcap_{i \in T} S_i \right|=X!2^Y\) 。

\(G\) の連結成分が全てパスグラフであるかを判定する際に愚直に \(N\) 頂点のグラフを全て作ると TLE となることに注意してください。どの辺にも繋がっていないような頂点を考えないことで計算量を削減することができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

from collections import defaultdict

mod = 998244353
n, m = map(int, input().split())
fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = i * fact[i - 1] % mod
aa = []
for i in range(m):
    x, y = map(int, input().split())
    aa.append((x - 1, y - 1))
ans = 0
for bi in range(1 << m):
    g = defaultdict(lambda: [])
    s = set()
    fu = 1
    for i in range(m):
        if (bi >> i) & 1:
            g[aa[i][0]].append(aa[i][1])
            g[aa[i][1]].append(aa[i][0])
            s.add(aa[i][0])
            s.add(aa[i][1])
            fu = -fu
    ss = len(s)
    ok = True

    def f(i, co):
        global ok
        s.remove(i)
        li = []
        for x in g[i]:
            if x == co:
                continue
            li.append(x)
        if len(li) == 0:
            return
        if len(li) == 1:
            f(li[0], i)
            return
        ok = False

    st = -1
    cc = n - ss
    res = fu
    for i, gg in g.items():
        if not ok:
            break
        if len(gg) == 1 and i in s:
            f(i, -1)
            cc += 1
            res = 2 * res % mod
    ok &= len(s) == 0
    if not ok:
        continue
    ans += res * fact[cc] % mod
print(ans % mod)