Notice this problem can be visualized by viewing the action of "swapping" as travelling along an edge on a graph with node ~1~ as Shirogane and node ~N~ as Kaguya.

Subtask 1

For the first ~30\%~, we loop through each hat color from ~1~ to ~N~ and calculate the cost to swap both Kaguya and Shirogane's hat to color ~i~.

We can simulate this process by first letting Shirogane swap to the closest person with color ~i~. And then let Kaguya swap to the closest person to him with color ~i~ that hasn't been swapped with Shirogane already. Notice this might not produce the best answer for color ~i~, and we also have to do it but with Kaguya going first and Shirogane going second. Then we can take the minimum of the two results to get the minimum cost for color ~i~.

For each case, we can run breadth-first search once for each person to find the closest hat still available to that person, resulting in a time complexity of ~\mathcal O(NM)~.

Subtask 2

To get full score, we have to optimize the process of searching for the best answer for each hat color. Notice that there are two main cases of an optimal answer for some hat color ~i~:

1. The closest hat of color ~i~ from node ~1~ (Shirogane) and ~N~ (Kaguya) are different. In this case they both take the closest hat to them.
2. The closest hat of color ~i~ from both of them are the same. In this case we have to let a person take their second closest choice.

So we have to keep track of the closest and second closest node of each hat color for both Shirogane and Kaguya, which can be done by running breadth-first search once from node ~1~ and once from node ~N~. Then we can calculate the optimal answer for each hat color in ~\mathcal O(1)~ by considering the aforementioned two cases, resulting in a time complexity of ~\mathcal O(N+M)~.