This problem is an exercise of the \(\exp\) (exponential) of a formal power series (FPS).

For a FPS \(f\) where \([x^0]f=0\), \(\exp(f)\) is defined as follows:

• \(\displaystyle \exp(f) = \sum_{n=0}^\infty \frac{f^n}{n!}\).

The first \(N\) terms of \(\exp(f)\) can be computed in an \(\mathrm{O}(N\log N)\) time using Newton’s method, just as finding the inverse of an FPS using Newton’s method (see also the editorial of ABC 260-Ex).

Now we will move on to the original problem.

---

The answer to the problem is found as (the number of all test cases) \(-\) (the number of test cases for which Alice’s solution is AC and Bob’s is WA) \(-\) (the number of those for which Bob’s is AC and Alice’s is WA) \(+\) (the number of those for which both Alice’s and Bob’s are AC).

By symmetry, (the number of test cases for which Alice’s solution is AC and Bob’s is WA) \(=\) (the number of those for which Bob’s is AC and Alice’s is WA), so it is sufficient to find (the number of test cases for which Alice’s solution is AC and Bob’s is WA) and (the number of those for which both Alice’s and Bob’s are AC).

The built graph turns out to form several cycles. Since the cycles are independent, we consider whether Alice and Bob’s solutions yield the correct answer for each cycle.

A cycles is of one of the following four types:

• Both Alice’s and Bob’s solution yield the correct answer.
• Only Alice’s yields the correct answer.
• Only Bob’s yields the correct answer.
• Both Alice’s and Bob’s solution yield a wrong answer.

We seek for the number of inputs consisting of zero or more cycles for which both solutions yield the correct answer and of one or more cycles for which only Alice’s yields the correct answer.

If both solutions yield the correct answer for a cycle, it contains only one vertex.

Also, if Alice’s one alone yields the correct answer, it contains two or more vertices, and the weight of the outgoing edge from the vertex with minimum index is the maximum weight among those in the cycle.

Based on the observations so far, we consider the count.

First, we consider the number of inputs consisting of zero or more cycles for which both solutions yield the correct answer and of one or more cycles for which only Alice’s yields the correct answer

When the input has \(C_i\) cycles of size \(i\), the answer can be expressed as:

\[(N!\prod_{i=1}^N \frac{1}{i!^{C_i}}) (\frac{1}{(\sum_{i=1}^N C_i)!}) (\prod_{i=1}^N (i-1)!^{C_i})(N!\prod_{i=1}^N\frac{1}{i}^{C_i}). \]

We will describe this expression.

First, \((N!\prod_{i=1}^N \frac{1}{i!^{C_i}})\) expresses the number of ways to assign vertex number to each cycle; that is, a multinomial coefficient.

Next, \( \frac{1}{(\sum_{i=1}^N C_i)!}\) is needed because there are \((\sum_{i=1}^N C_i)!\) freedom to arrange the cycles.

\(\prod_{i=1}^N (i-1)!^{C_i}\) expresses the assignments of the weights to the edges. Among the \(N!\) assignments, \(\frac{1}{c}\) of them satisfies the condition that Alice’s solution is AC for a cycle of length \(c\).

In order to find the sum over all \(C\), we use FPS. The expression above can be deformed into:

\[N!^2 \frac{1}{(\sum_{i=1}^N C_i)!}\prod_{i=1}^N (\frac{1}{i^{2}})^{C_i}.\]

With \(f(x) = \sum_{i=1}^N \frac{1}{i^2}x^i\), what we want is \(N!^2[x^N]1 + f(x) + \frac{f(x)^2}{2!} + \frac{f(x)^3}{3!} + \ldots\), which equals \(N!^2 [x^N]\exp(f(x))\).

Actually, we wanted to count the inputs containing one or more cycles for which only Alice’s yields the correct answer. Nevertheless, it does not matter because it easily turns out that there are \(N!\) inputs which contains zero cycles for which only Alice’s yields the correct answer and in which both solutions yields the correct answer for all cycles.

Summary

Let \(f(x) = \sum_{i=1}^N \frac{1}{i^2}x^i\).

Total number of inputs: \(N!^2\)

The number of inputs for which Alice’s solution is AC and Bob’s is WA: \((N!^2 [x^N]\exp(f(x))) - N!\)

The number of inputs for which Alice’s solution is WA and Bob’s is AC: \((N!^2 [x^N]\exp(f(x))) - N!\)

The number of inputs for which both solutions are AC: \(N!\)

Hence, the answer is \(N!^2 (1 - 2 [x^N]\exp(f(x)) )) +N!\).