Solution

Firstly, there must be no common points between the circuits. Otherwise, if two circuits of length \(a\) and \(b\) with common points have \(k\) common edges, they form a circuit of length \(a+b-2k\), and \(a, b\) are both prime and not \(2\), so \(a+b-2k\) is even and not \(2\), which is definitely not prime. So after shrinking the circuit, a legal graph must be a tree.

If there are \(m\) circuits in the graph, and the length of the \(i\)-th circuit is \(s_i\), then the number of ways to connect them into a tree is shown by Extended Cayley’s Theorem:

\[ \#\text{(connect the circuits into a tree)}=n^{m-2}\prod_{i=1}^ms_i=\dfrac{\prod_{i=1}^m ns_i}{n^2} \]

Then the answer is:

\[ \dfrac 1{n^2}\sum_{s_1\dots s_m}\dbinom{s_1+\cdots+s_m}{s_1,\cdots,s_m}\prod_{i=1}^m ns_iC(s_i) \]

where \(s_i=1\) or \(s_i\) is a prime number not less than 3, and \(C(i)=\begin{cases}\frac{(i-1)!}2&i>1\\1&i=1\end{cases}\) denotes the number of ways to connect \(i\) points into a circuit.

Consider the exponential generating function of a single circuit:

\[ F(x)=\sum\limits_{i=1\vee i\ge 3,i\in\mathbf P}niC(i)\dfrac{x^i}{i!}=nx+\sum\limits_{i\ge 3,i\in\mathbf P}\dfrac n2x^i \]

Then the exponential generating function of answer is:

\[ G(x)=\dfrac 1{n^2}\sum\limits_{m\ge 0}\dfrac{F(x)^m}{m!}=\dfrac 1{n^2}\exp F(x) \]

We recall that polynomial exp can be calculated in \(O(n\log n)\) time, so the total time complexity is \(O(n\log n)\).

Another Solution

According to the official editorial, the answer is:

\[ \left[\dfrac{x^n}{n!}\right]F(x) \]

where

\[ F(x)=G(x\exp F(x)),\ G(x)=x+\sum\limits_{p\ge 3,p\in\mathbf P}\dfrac{x^p}2 \]

let \(H(x)=x\exp F(x)\),

\[F(x)=G(H(x))\]

\[H(x)=x\exp G(H(x))\]

\[\dfrac{H(x)}{\exp G(H(x))}=x\]

\[H^{\langle-1\rangle}(x)=\dfrac{x}{\exp G(x)}\]

apply the Lagrange Inversion Formula:

\[\left[x^n\right]G(H(x))=\dfrac 1n[x^{n-1}]G'(x)\left(\dfrac{H^{\langle-1\rangle}(x)}x\right)^{-n}=\dfrac 1n[x^{n-1}]G'(x)\left(\exp G(x)\right)^n\]

which can be calculated in \(O(n\log n)\).