首先考虑点双计数。

肯定要考虑容斥，但是我们不太好钦定割点集合。

考虑钦定最小割点。

设 $F_{i, S}$ 表示 $S$ 导出子图内，点连通并且没有 $\le i$ 的割点的方案数。初始 $F_{0, S}$ 为 $S$ 连通的方案数。若钦定 $i$ 为割点，则删除它后至少裂成两个连通块，相当于做一个集合幂级数的 $\exp$。另一个方面，也可以看做去除能分裂的方案，相当于求 $\ln$。

以及一些常数优化：由于只有一项的变化，不需要整体重做 FWT，可以根据原来 FWT 的结果算。

边双计数也可以用类似方法。

回到原题，我们先钦定 $2 \sim n - 1$ 的点都不是割点，然后钦定 $2 \sim n - 1$ 的点满足裂开形成的连通块要么同时包含 $1, n$ 要么同时不包含，即求 $\exp$。

时间复杂度 $O(2^n n^3)$ 或 $O(3^n n)$。