E - Biconnected Graph Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 1900 点

問題文

整数 N と素数 P が与えられます。

1 から N までの番号がついた N 頂点の連結無向グラフであって以下の条件を満たすものの個数を P で割った余りを求めてください。

  • G に自己辺はない。なお、多重辺はあってもよい。
  • G のすべての辺 (u,v) について、(u,v) を G から削除しても G は連結なままである。すなわち、G は二重辺連結である。
  • G のすべての辺 (u,v) について、(u,v) を G から削除すると G は二重辺連結でなくなる。

二つのグラフは、異なる頂点の組 (u,v) であって二つのグラフで u と v を結ぶ辺の本数が異なるものが存在するとき、またそのときに限り異なるとします。

制約

  • 2 \le N \le 50
  • 10^9<P<1.01\times 10^9
  • P は素数である。
  • すべての入力値は整数である。

入力

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

N P

出力

答えを出力せよ。

入力例 1

2 1005976817

出力例 1

1

入力例 2

5 1000837403

出力例 2

372

入力例 3

10 1001160547

出力例 3

789846604

入力例 4

20 1006779551

出力例 4

888612770

Score : 1900 points

Problem Statement

You are given an integer N and a prime P.

Count the number, modulo P, of undirected connected graphs G of N vertices numbered 1 to N that satisfy the following condition:

  • There are no self-loops in G. Note that multiple edges are allowed.
  • For all edges (u,v) in G, if we delete (u,v) from G, G remains connected. In other words, G is edge-biconnected.
  • For all edges (u,v) in G, if we delete (u,v) from G, G is no longer edge-biconnected.

Two graphs are considered different if and only if there exists a pair of distinct vertices (u,v) such that the numbers of edges connecting u and v in the two graphs are different.

Constraints

  • 2 \le N \le 50
  • 10^9<P<1.01\times 10^9
  • P is prime.
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N P

Output

Print the answer.

Sample Input 1

2 1005976817

Sample Output 1

1

Sample Input 2

5 1000837403

Sample Output 2

372

Sample Input 3

10 1001160547

Sample Output 3

789846604

Sample Input 4

20 1006779551

Sample Output 4

888612770