/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の頂点と M 本の辺からなる単純（自己ループおよび多重辺を持たない）かつ連結な無向グラフが与えられます。
i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結びます。
下記の 2 つの条件をともに満たす整数列 (A_1, A_2, \ldots, A_k) を長さ k のパスと呼びます。
- すべての i = 1, 2, \dots, k について、1 \leq A_i \leq N 。
- すべての i = 1, 2, \ldots, k-1 について、頂点 A_i と頂点 A_{i+1} は辺で直接結ばれている。
空列も長さ 0 のパスとみなします。
S = s_1s_2\ldots s_N を 0 と 1 のみからなる長さ N の文字列とします。 パス A = (A_1, A_2, \ldots, A_k) が下記を満たすとき、パス A を S に関する良いパスと呼びます。
- すべての i = 1, 2, \ldots, N について、次を満たす。
- s_i = 0 ならば、A に含まれる i の個数は偶数である。
- s_i = 1 ならば、A に含まれる i の個数は奇数である。
S として考えられる文字列（すなわち、0 と 1 のみからなる長さ N の文字列）は 2^N 個ありますが、そのすべてにわたる「 S に関する良いパスのうち最短のものの長さ」の総和を出力してください。
この問題の制約下において、0 と 1 からなる長さ N のどのような文字列を S として選んでも、S に関する良いパスが少なくとも 1 つ存在することが示せます。
制約
- 2 \leq N \leq 17
- N-1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq u_i, v_i \leq N
- 与えられるグラフは単純かつ連結
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
14
- S = 000 のとき、空列 () は S に関する最短の良いパスであり、その長さは 0 です。
- S = 100 のとき、(1) は S に関する最短の良いパスであり、その長さは 1 です。
- S = 010 のとき、(2) は S に関する最短の良いパスであり、その長さは 1 です。
- S = 110 のとき、(1, 2) は S に関する最短の良いパスであり、その長さは 2 です。
- S = 001 のとき、(3) は S に関する最短の良いパスであり、その長さは 1 です。
- S = 101 のとき、(1, 2, 3, 2) は S に関する最短の良いパスであり、その長さは 4 です。
- S = 011 のとき、(2, 3) は S に関する最短の良いパスであり、その長さは 2 です。
- S = 111 のとき、(1, 2, 3) は S に関する最短の良いパスであり、その長さは 3 です。
よって、求める答えは 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14 です。
入力例 2
5 5 4 2 2 3 1 3 2 1 1 5
出力例 2
108
Score : 500 points
Problem Statement
You are given a simple connected undirected graph with N vertices and M edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
A sequence (A_1, A_2, \ldots, A_k) is said to be a path of length k if both of the following two conditions are satisfied:
- For all i = 1, 2, \dots, k, it holds that 1 \leq A_i \leq N.
- For all i = 1, 2, \ldots, k-1, Vertex A_i and Vertex A_{i+1} are directly connected by an edge.
An empty sequence is regarded as a path of length 0.
Let S = s_1s_2\ldots s_N be a string of length N consisting of 0 and 1. A path A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to S if the following conditions are satisfied:
- For all i = 1, 2, \ldots, N, it holds that:
- if s_i = 0, then A has even number of i's.
- if s_i = 1, then A has odd number of i's.
There are 2^N possible S (in other words, there are 2^N strings of length N consisting of 0 and 1). Find the sum of "the length of the shortest good path with respect to S" over all those S.
Under the Constraints of this problem, it can be proved that, for any string S of length N consisting of 0 and 1, there is at least one good path with respect to S.
Constraints
- 2 \leq N \leq 17
- N-1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq u_i, v_i \leq N
- The given graph is simple and connected.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print the answer.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
14
- For S = 000, the empty sequence () is the shortest good path with respect to S, whose length is 0.
- For S = 100, (1) is the shortest good path with respect to S, whose length is 1.
- For S = 010, (2) is the shortest good path with respect to S, whose length is 1.
- For S = 110, (1, 2) is the shortest good path with respect to S, whose length is 2.
- For S = 001, (3) is the shortest good path with respect to S, whose length is 1.
- For S = 101, (1, 2, 3, 2) is the shortest good path with respect to S, whose length is 4.
- For S = 011, (2, 3) is the shortest good path with respect to S, whose length is 2.
- For S = 111, (1, 2, 3) is the shortest good path with respect to S, whose length is 3.
Therefore, the sought answer is 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14.
Sample Input 2
5 5 4 2 2 3 1 3 2 1 1 5
Sample Output 2
108