AT_agc065_f [AGC065F] Always Perfect
题目描述
给定一个偶数 $N$ 和一个素数 $M$。
请你求出满足以下条件的 $N$ 个顶点、编号为 $1$ 到 $N$ 的简单连通无向图 $G$ 的个数，并对 $M$ 取模。
- 对于 $G$ 的任意一棵生成树 $T$，$T$ 上都存在一个完全匹配。
什么是图的完全匹配？对于图 $G$，完全匹配是指由 $G$ 的边组成的一个集合 $E$，使得对于图中每个顶点 $v$，恰好有一条以 $v$ 为端点的边属于 $E$。
输入格式
输入以以下格式从标准输入读入。
> $N$ $M$
输出格式
请输出答案。
说明/提示
### 限制条件
- $2 \leq N \leq 500$
- $10^8 \leq M \leq 10^9$
- $N$ 是偶数
- $M$ 是素数
- 输入的所有值均为整数
### 样例说明 1
例如，下图中展示的两个图，左侧的图满足条件。而右侧的图，由于其红色粗线表示的包含 $3$ 条边的生成树上不存在完全匹配，因此不满足条件。
由 ChatGPT 4.1 翻译