Problem

You're given a set of hotel rooms, each room has it's own priority and each room has a client.

You have to minimize the number of repeating clients in the hotel rooms, according to the rules:

• You can only swap clients with the same priority.
  
• You are not allowed to swap rooms.
  
• You are not allowed to swap priorities.
  

Limitations:
0 < Rooms < 1000
0 < Priority < 10^9
'A' < Client < 'Z'

Example

Input:

Output:

The following example shows:
- in the picture1 — client "B" is repeating.
- in the picture2 — there are no repeating clients.

Thoughts

1. I converted it to the graph and tried DFS + Multiset, but the complexity was exponential
   
   
2. Tried to create a solution using randomization, but I didn't get to it.
   
3. I googled and didn't find similar problems.