First, the task is obviously impossible if there is a person who is initially tired and has an “incorrect” piece of baggage. It turns out it is always possible otherwise.

Consider the graph where there is an edge from \(i\) to \(p_i\) for each Person \(i\). Since \(p\) is a permutation of \(1, \ldots, n\), it is a set of cycles. Let \(C\) be the number of cycles.

Let us think of a lower bound of the number of operations. Even if tired people can take part in operations, we need at least \(N-C\) operations, so we do need at least \(N-C\) operations. Actually, we can construct a sequence of \(N-C\) operations, as follows.

Let us treat each cycle separately. It is important to notice the following:

• When an operation is done with two untired people \(i, j\), Person \(i\) does not get tired if \(a_i \geq a_j\).

From this fact, if we choose the lightest person \(i\) in a cycle, we can reduce the problem to a problem with one less vertex in the cycle. We are done when the cycle has just one vertex, so we can achieve the objective within the cycle with \(n-1\) operations, where \(n\) is the initial number of vertices in the cycle.

By doing this for each cycle, we can achieve the whole objective with \(N-C\) operations.

For explanation, we separately treated each cycle, but when implementing the solution, we can just give the correct pieces of baggage to the people in ascending order of weight.