shelf[i] is the code of the item at position i. A layout plan plan of the same length says that position i should hold item plan[i].
You cannot rearrange items freely, only along allowed links: each pair links[k] = [a, b] lets you swap the items at positions a and b. Every link may be used any number of times, in any order.
A mismatch is a position i where shelf[i] != plan[i]. Return the smallest number of mismatches you can reach with swaps.shelf=[7, 3, 9, 3], plan=[3, 7, 3, 9], links=[[0, 1], [1, 2]] → 2
Positions 0, 1 and 2 are chained together, so items 7, 3, 9 can be arranged among them freely, e.g. [3, 7, 9, 3]. Positions 0 and 1 match, while position 2 holds 9 instead of 3 and position 3 holds 3 instead of 9. That is 2 mismatches.
shelf=[5, 6, 5], plan=[6, 5, 5], links=[] → 2
No swaps are allowed, so positions 0 and 1 stay different.
shelf=[4, 8, 2, 6], plan=[6, 2, 8, 4], links=[[0, 3], [2, 1]] → 0
Swap positions 0 and 3, then 1 and 2, and the shelf matches the plan exactly.
len(shelf) = len(plan) = n ≤ 10⁵shelf[i], plan[i] ≤ 10⁵len(links) ≤ 10⁵links[k] = [a, b], 0 ≤ a, b ≤ n − 1, a ≠ bshelf=[7, 3, 9, 3], plan=[3, 7, 3, 9], links=[[0, 1], [1, 2]]
2
Run checks the first 3 tests in your browser. Submit checks all 81 tests on the server, hidden ones included.