Let’s consider the operations in reverse order.

Consider a graph where we draw an edge from \(i\) to \(A_i\). Think about how this graph changes when we reverse the operation for \(i = N\).

Focus on vertex \(N\). First, consider whether vertex \(N\) is included in a cycle.

• If vertex \(N\) is included in a cycle: The balls in this cycle correspond to those that were in box \(N\) before the operation. We break this cycle and add edges from the vertices on the cycle to vertex \(N\).
• If vertex \(N\) is not included in a cycle: Some cycle corresponds to the balls that were in box \(N\) before the operation. We break this cycle and add edges from the vertices on the cycle to vertex \(N\). Here, it’s also permissible to assume that box \(N\) was empty and change nothing.

In either case, if there exists a “child” of vertex \(N\) (a vertex that extends an edge to vertex \(N\) and is not included in a cycle), it’s impossible to reverse the operation, and we can conclude that the answer is No.

When vertex \(N\) is not included in a cycle, there is freedom in choosing which cycle to break, but here, let’s suppose we use the cycle in the connected component that includes vertex \(N\).

Let’s consider the conditions under which we can complete the reversal for \(i = N, N-1, \cdots, 1\) when the operation can only be reversed in this form.

Then, as a sufficient condition, we obtain that the following property holds for each vertex \(v\):

• Let \(u_1, \cdots, u_k\) be the children of \(v\). Let \(w_i\) be the largest numbered vertex in the subtree rooted at \(u_i\). Then, \(v < w_i\).

In fact, this condition is also a necessary condition in the original problem (without limiting the form of the reversal operation). Therefore, by simply checking this condition, we can solve the problem.

We will show that this condition is necessary. Take a vertex \(v\) that does not satisfy the condition and its child \(u\). No matter how we reverse the operations for \(i = N, N-1, \cdots, v + 1\), they will not affect the subtree rooted at vertex \(u\). Then, consider \(i = v\), and \(v\) will have a child \(u\), so the reversal fails. This shows the necessity.

The condition can be checked in \(O(N)\) time.

Sample Solution (C++)

Bonus: The number of valid \(A\) is \((2N - 1)!!\). Try proving it.