If we try to delete an edge, the remaining graph will be a chain after shrinking biconnected components (a cycle if adding it back).

We consider solving the problem for every biconnected component and multiplying the answer.

In the subproblem there is an additional edge between two vertices, because they can reach each other through the cycle.

Using this method repeatedly. Each time taking an edge connected to vertex \(1\). Then we will get subproblems of the following format:

• Count good graphs of \(n\) vertices, addtionally, the first \(k\) vertices can reach each other on the outside.

Now we need to consider how the first \(k\) vertices are distributed:

• \(\forall 1\le u,v\le k\)，\(C(u),C(v)\) are not adjacent in the cycle. Where \(C(u)\) is the biconnected component that contains \(u\).

We can DP through the cycle. Note that we didn’t constrain which edge to be picked, so that every good graph is calculated for exactly \(\deg(1)\) times. So we should store \(\deg(1)\) in the DP state addtionally and finally divide the answer by it.

Time complexity: \(O(n^5)\). \(O(n^6)\) solutions with small constant may pass.