問題一覧 > 通常問題

No.2507 Yet Another Subgraph Counting

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : suisensuisen / テスター : 👑 emthrmemthrm torisasami4torisasami4 rniyarniya
1 ProblemId : 10029 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-02 03:49:45

問題文

頂点に 1,2,,n1,2,\ldots,n の番号が、辺に 1,2,,m1,2,\ldots,m の番号が付いた nn 頂点 mm 辺の単純無向グラフがあります。辺 ii は頂点 uiu _ i と頂点 viv _ i を双方向に結んでいます。

suisen 君は mm 本の辺のうち 00 本以上を 赤く 塗り、それ以外の辺を 青く 塗ります。以下では 赤い 辺のみからなる単純閉路のことを単に 赤い 閉路 と呼びます。

suisen 君の辺の塗り方のうち、以下の条件を満たすものの個数を求めてください。

  • 任意の相異なる 22 つの 赤い 閉路に対して、その両方に含まれる頂点は存在しない。

ここで、22 つの 赤い 閉路に対して、その一方にしか含まれない辺が存在するとき、かつそのときに限り 22 つの 赤い 閉路は異なるものとします。

なお、本問題の制約下で、答えは 2632^{63} 未満であることを証明できます。

入力

入力は以下の形式で標準入力から与えられます。

n mn\ m
u1 v1u _ 1\ v _ 1
u2 v2u _ 2\ v _ 2
\vdots
um vmu _ m\ v _ m
  • 入力は全て整数で与えられる。
  • 与えられるグラフは単純である。
  • 2n132\leq n\leq 13
  • 1mn(n1)21\leq m\leq \dfrac{n(n - 1)}{2}
  • 1ui<vin1\leq u _ i \lt v _ i \leq n
  • iji \neq j ならば (ui,vi)(uj,vj)(u _ i, v _ i) \neq (u _ j, v _ j)

出力

答えを 11 行に出力し、改行してください。

サンプル

サンプル1
入力
6 7
1 4
1 5
2 5
3 5
3 6
4 5
5 6
出力
126

この入力は次のグラフを表しています。

例えば辺 1,2,3,4,6,71,2,3,4,6,7赤く 塗り、辺 55青く 塗った場合は次の図のようになります。このとき、赤い 閉路は辺 1,2,61,2,6 からなるものしかありません。従って、この塗り方は条件を満たします。

他の例として、辺 1,2,4,5,6,71,2,4,5,6,7赤く 塗り、辺 33青く 塗った場合は次の図のようになります。このとき、赤い 閉路は辺 1,2,61,2,6 からなるものと辺 4,5,74,5,7 からなるものの 22 つ存在します。この 22 つの閉路はともに頂点 55 を含むため、この塗り方は条件を満たしません。

辺の塗り方は全部で 2m=1282 ^ m = 128 通りありますが、条件を満たさない塗り方は次の 22 通りしかありません。

  • 1,2,4,5,6,71,2,4,5,6,7赤く 塗り、辺 33青く 塗った場合
  • 全ての辺を 赤く 塗った場合

従って、この入力に対する答えは 1282=126128 - 2 = 126 です。

サンプル2
入力
6 10
1 2
1 3
1 4
1 5
2 3
2 4
2 6
3 5
4 6
5 6
出力
816

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。