Tutte-Berge 公式指出，无向图 $G=(V,E)$ 的最大匹配为 $\frac12\min_{U\subseteq V}\{|U|-odd(G-U)+|V|\}$，其中 $odd(H)$ 表示 $H$ 中大小为奇数的连通块数。

原图的最大匹配为 $n-1$，因此 $\min_{U\subseteq V}\{|U|-odd(G- U)\}=-2$。考虑这样的一个点集 $U$，如果其中某个点的度数不为 $2n-1$，则加入以它作为端点的一条边后这个值不变，不合法。同理，$G-U$ 的每个连通块都是大小为奇数的团。

假设有 $k$ 个度数为 $2n-1$ 的点，则剩余有 $k+2$ 个奇数大小的团。把每个团的大小加一，则团的总点数为 $2n+2$，且大小均为偶数。由于至少有两个团，因此方案数为 $P(n+1)-1$。

利用五边形数定理和多项式求逆求解即可。时间复杂度 $O(n\log n)$。