During the contest, I got the idea that we can start with an all first arrangement, and gradually improve it step by step, until we reach a final form.

What I missed is to prove that the each step will replace some a with b, and not versa(!), if a solution exists

1. If two share the same first form, then both must choose the second form, because if one chooses first form and one chooses 2nd form, the
   extra rule in the problem will be violated

2. Therefore, we can just discover all first form collisions, and replace them with second form

3. After that, we can not revert any second form to first form, because that would mean the reverted first form has another second form
   whose first form is same as this reverted first form (same reasoning as in step 1)

4. This means, from now on, if we have any collsions of second form, we know we can not make any other changes, and thus answer is no

5. This also means, from now on, if we have a collision of first form and second form, we can only go from first to second, and not second
   to first

6. So we scan again, and update all the second form collision, and then a final scan for sanity check

Now for the soundness and completeness proof

1. If the algo gives YES, of course, there will be no collsion, because each step solves one of the 3 possible cases of collisions  => the
   algorithm is sound
 

2. If a solution does exist, and our algo gives no => this means we discover a second form collision,

3. If this second form collsion is from a first form collsion, then by our rules we can have no answer => contradition

4. If the second form collsion is the result of fixing a first-second form collsion, similar to the reasoning we give in the algorithm. we are there because
   any other option will yield an NO, i.e., we know for each change we made, it HAS TO be in any solution => contradiction

5. This also means our algo gives the mimium number of changes

But implementation wise, every time we switch from a first form to a second form, we may potentially introduce new conflicts between the newly-introduced second form and existing first form. Therefore, this switch should be done is a graph-like, event-driven way. Instead of scanning the array once and call it done!

validate(v)
  if v uses first form
      done

  if v uses second form
      loop all u in  1...n save v
      if u uses first form, and first(u) = second(v)
          mark u to use second form
          validate(u)

The for loop will be triggered O(n) times, with each one O(n) run time => O(n^2) in total