The basic idea is the “union by size / small to large” heuristic. That is, imagine we merely kept track of where each ball is using an array, and that operation \(1\ X \ Y\) is only called such that the number of balls in box \(Y\) is not more than the number of balls in box \(X\). Then whenever a ball moves, the number of balls in its new box always ends up to be at least twice of the number of balls that was in the box it moved from. Since there is an upper bound of \(O(N+Q)\) balls that ever enter boxes, each ball can only move \(O( \log (N+Q))\) times, and therefore the total time spent processing moves won’t exceed \(O((N+Q) \log (N+Q))\).

How to handle the original problem where box \(Y\) could have more balls than box \(X\)? We need some way of quickly swapping all the balls in the boxes before we do the merging, but there is no easy way to update the locations of all the balls. Instead, we imagine \(N\) bags numbered \(1\) to \(N\), where box \(i\) initially contains bag \(i\), which contains ball \(i\). Instead of keeping track which box each ball is in, we track which bag each ball is in. We also track which box each bag is in, and the current bag that each box holds. That way, we can swap bags between boxes in \(O(1)\), and ensure we never move balls from larger bags to smaller ones.