AT_codequeen2025_final_f アクリルスタンド

アイドルグループ Bit♡Beat のファンである高橋君はメンバー $ N $ 人全員のアクリルスタンドを $ 1 $ つずつ持っています。 高橋君は $ N $ 個のアクリルスタンドを一列に並べようとしていますが、特定の $ 2 $ 人を隣に並べてはいけないと考えています。具体的には、 $ i=1,2,\ldots,M $ に対し $ A_i $ 人目のメンバーと $ B_i $ 人目のメンバーのアクリルスタンドが隣り合わないように並べたいと考えています。 高橋君の $ M $ 個の要望を全て満たすような $ N $ 個のアクリルスタンドの並べ方が何通りあるかを $ 998244353 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

答えを出力せよ。

### Sample Explanation 1 以下の $ 2 $ つの並べ方が条件を満たします。 - $ 2 $ 人目のメンバー、 $ 3 $ 人目のメンバー、 $ 1 $ 人目のメンバーのアクリルスタンドと順に並べる。 - $ 1 $ 人目のメンバー、 $ 3 $ 人目のメンバー、 $ 2 $ 人目のメンバーのアクリルスタンドと順に並べる。 したがって、 $ 2 $ を出力してください。 ### Sample Explanation 2 条件を満たす並べ方は存在しません。したがって、 $ 0 $ を出力してください。 ### Sample Explanation 3 $ 998244353 $ で割ったあまりを出力してください。 ### Constraints - $ 2\le N\le 10^6 $ - $ 0\le M\le 16 $ - $ 1\le A_i < B_i \le N $ - $ (A_i , B_i) \neq (A_j , B_j) $ $ (i \neq j) $ - 入力される値は全て整数である