If we could find for each \(0 \leq k \leq N\) the total number of permutations such that \(r_i = p_i\) or \(r_i = q_i\) holds for some \(k\) indices, then we can compute the answer by the inclusion-exclusion principle.

Let \(i_1, i_2 ,\dots, i_k\) be fixed indices determined to be \(r_i = p_i\) or \(r_i = q_i\). Let us find the total number of assignments of distinct values to \(r_i\) for these indices.

For each \(i = i_1, \dots, i_k\), let us regard \((p_i, q_i)\) as an edge of a \(N\)-vertices graph. It is sufficient to compute the total number of assignments of each edge to one of its endpoints such that no two distinct edges shares a vertex assigned to it.

We consider each connected component, except for isolated vertices and self-loops. Since the maximum degree of the graph is at most two, a connected component is:

• a single cycle, in which case there are \(2\) possible assignments; or
• a single path, in which case there are \(L\) possible assignments, where \(L\) denotes the path’s length.

So the total number of such assignments is their product.

Now, we have to find the sum the value described above over all possible combinations of \(i_1, i_2 ,\dots, i_k\). We consider a graph with all the edges \((p_i, q_i)\) added, and determine for each connected component how many edges are chosen. Let \(K\) be the size of a connected component. If we know for each \(0 \leq k \leq K\) the total number of assignments of \(r_i\) when \(k\) edges are chosen out of the connected component, then the necessary values can be computed with a simple DP (Dynamic Programming). Hereinafter we assume that the graph is a single cycle.

When all the edges are chosen, there are \(2\) assignments, by the discussion above. Otherwise, the graph is a set of paths and isolated vertices, so the number of assignments is the product of their sizes. This is equivalent to the total number of ways of choosing a vertex from each connected component formed by arbitrarily-chosen edges and marking it, so it can be expressed as the sum a binomial coefficients. When counting, we can fix the minimum index of unused edges to regard the cycle as a path in the calculation.

Sample code (C++)