AT_abc199_d [ABC199D] RGB Coloring 2

[problemUrl]: https://atcoder.jp/contests/abc199/tasks/abc199_d $ N $ 頂点 $ M $ 辺の単純無向グラフがあります。頂点には $ 1 $ から $ N $ までの、辺には $ 1 $ から $ M $ までの番号がついています。 辺 $ i $ は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 このグラフの各頂点を赤、緑、青の $ 3 $ 色のいずれかで塗る方法であって、以下の条件を満たすものの数を求めてください。 - 辺で直接結ばれている $ 2 $ 頂点は必ず異なる色で塗られている なお、使われない色があっても構いません。

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

答えを出力せよ。

### 制約 - $ 1\ \le\ N\ \le\ 20 $ - $ 0\ \le\ M\ \le\ \frac{N(N\ -\ 1)}{2} $ - $ 1\ \le\ A_i\ \le\ N $ - $ 1\ \le\ B_i\ \le\ N $ - 与えられるグラフは単純 (多重辺や自己ループを含まない) ### Sample Explanation 1 頂点 $ 1,\ 2,\ 3 $ の色をそれぞれ $ c_1,\ c_2,\ c_3 $ とし、赤、緑、青をそれぞれ `R`, `G`, `B` で表すと、以下の $ 6 $ 通りが条件を満たします。 - $ c_1c_2c_3\ = $ `RGB` - $ c_1c_2c_3\ = $ `RBG` - $ c_1c_2c_3\ = $ `GRB` - $ c_1c_2c_3\ = $ `GBR` - $ c_1c_2c_3\ = $ `BRG` - $ c_1c_2c_3\ = $ `BGR` ### Sample Explanation 2 辺がないため、各頂点の色を自由に決めることができます。 ### Sample Explanation 3 条件を満たす塗り方が存在しない場合もあります。 ### Sample Explanation 4 答えは $ 32 $ ビット符号付き整数型に収まらないことがあります。