Consider a graph \(G\) where \(1,\ldots,N\) are vertices and there is an edge between each \((P_i,Q_i)\). The original problem can be reworded as: “how many subsets \(E\) of edges are there such that it is an edge cover?” Obviously, this can be considered for each connected component.

Since \(P,Q\) are both permutations of \((1,\ldots,N)\), the degree of every vertex is \(2\), so the graph is a set of cycles. Therefore, it is sufficient to solve the problem for a cycle.

We consider the following problem first, as we are using it later.
“you will choose some of the elements from \(1,2,\ldots,M\). Here, for every pair of two consecutive numbers, at least one of them must be chosen. How many ways are there to do so?”
We can see that the answer to the problem \(f(M)\) satisfies \(f(1)=2,f(2)=3,f(M)=f(M-1)+f(M-2)\). (It can be understood by considering how whether or not choosing \(M\) affects to the combination from the remaining)

Let’s get back on track.
How many subsets of edges in an \(M\)-vertex graph whose vertices are \(1,\ldots,M\) form edge covers? This problem is quite similar to “you must choose one of adjacent elements. How many ways are there to do so?” that we discussed right before. Let \(g(M)\) be the answer. By dividing into cases depending on whether or not choosing Edge \((1,M)\), we can see that the answer satisfies \(g(1)=1,g(2)=3,g(3)=4,g(M)=f(M-1)+f(M-3)\).

Therefore, all \(f(M),g(M)\) in the range \(M\leq N\) can be computed in a total of \(O(N)\) time, so the problem has been solved in a total of \(O(N)\) time. By the way, by transforming the equations, we can show that \(g(N)=L_N\). (Here, \(L_N\) is Lucas number)