The state of drawers and items can be represented by a directed graph where the nodes are drawers and the edges are items. If an item is located in drawer ~A~, and its alternative is drawer ~B~, the graph contains the edge ~A \to B~. Given the fact that each drawer can contain a maximum of one item, the out-degree of all nodes is either ~0~ or ~1~, the path from any drawer is unambiguous and ends in an empty drawer or a cycle of drawers.

If drawer ~B~ is empty and there if an edge ~A \to B~, it is possible to store the item from drawer ~A~ to drawer ~B~, which corresponds to swapping edge ~A \to B~ with edge ~B \to A~. In other words, reversing the associated edge.

If there is a path from a full drawer ~A~ to an empty drawer ~B~, the drawer ~A~ can be emptied by repeatedly moving items, which corresponds to swapping edges on the path from ~A~ to ~B~.

If a path from a drawer ends in a cycle, that drawer cannot be emptied.

We need a data structure which can tell us whether it is possible to empty a drawer (or if it's empty already) or, in other words, is there a path in the graph to an empty drawer.

Let us mark ~final[l]~ the empty drawer which is the end of the path from drawer ~l~; additionally, if ~l~ is empty, then ~final[l] = l~, and if such a path doesn't exist, then ~final[l] = 0~ (an empty drawer ~0~ is added as a mark for a cycle).

When adding a new item, the following scenarios are possible:

1. If the item is being added in the empty drawer ~A~ whose alternative is drawer ~B~, then for each ~l~ where ~final[l] = A~, we change into ~final[l] = final[B]~.
2. If the drawer ~A~ needs to be emptied first and then add an item, the same thing happens.

A naive modification of the array final can be too slow for the limitations in this task.

The key thing is to notice how the drawers can be divided into classes considering the final drawer (drawers with equal final drawers are located in the same class), which enables us to implement the relation final efficiently with the union-find structure. A cycle is formed if we add an item whose drawers are both located in the same class.

With the help of the structure, we use a function ~find(l)~ which corresponds to the aforementioned array ~final[l]~ and function ~unite(a, b)~ which performs the substitution described in 1.

When we have defined these functions, the following can be applied:

• For an empty drawer, ~find(l) = l~.
• For a drawer that can be emptied, ~find(l) \ne 0~.
• A cycle is formed when adding items with drawers ~A~ and ~B~ if ~find(A) = find(B)~, and if it is added in the structure as ~unite(A, 0)~.
• Otherwise, a new cycle is not formed and we add the item as ~unite(A, B)~ (if we are adding the item in the drawer ~A~).