Brazil#6469
In Terry Gilliam's film "Brazil", we are introduced to a grim world ruled by an overgrown and inefficient bureaucratic system.
Although one can trace certain parallels with Orwell's dystopia "1984", the world of "Brazil" lacks the same terrifying efficiency. The bureaucracy is entirely dysfunctional, and society depends on outdated, barely functioning machines.
Overall, "Brazil" is definitely a film worth watching. Many of its scenes vividly depict the absurdity and meaninglessness of bureaucratic machinery.
Here are the main principles of the system:
There is an infinite number of bureaucrats, which we will number from to 10^9.
Each bureaucrat handles forms. A form is a sheet of paper with an identification number (ID) — an integer from to 10^9 inclusive. Multiple forms can share the same ID.
At any given moment, a bureaucrat can have zero or more forms arranged as a stack on their desk.
Citizens constantly come to bureaucrats to submit new forms. A new form is filled out and given to one of the bureaucrats, who places it on top of their stack.
From time to time, a bureaucrat may decide that their stack has grown too large. When another bureaucrat is momentarily distracted, the first one transfers their entire stack on top of the distracted colleague's stack (preserving the order of forms). After the transfer, the original stack becomes empty.
No form is ever processed. The forms simply circulate endlessly among the bureaucrats.
You are to simulate this system. The simulation consists of a sequence of queries of two types: either "bureaucrat receives a new form ", or "bureaucrat B_1 transfers all their forms to bureaucrat B_2". Initially, no bureaucrat has any forms.
Consists of at most 10^5 + 1 lines. Each line has one of the following formats:
— bureaucrat with ID receives a new form with ID and places it on top of their stack.
M~b_1~b_2 — bureaucrat with ID b_1 transfers their entire stack of forms to bureaucrat with ID b_2 (if b_1 has no forms, nothing happens).
— end of simulation. This line occurs exactly once and is always the last in the input.
Print the final state of all bureaucrats who have non-empty stacks by the end of the simulation. For each such bureaucrat, print a line of the form:
where is the bureaucrat's ID, and f_1, f_2, \ldots, f_n are the IDs of the forms on their desk, listed from top to bottom. The bureaucrats should be listed in increasing order of their IDs. Spaces must appear exactly where shown in the output format.
Let us examine the sequence of queries in the following example:
Bureaucrat receives a new form .
Bureaucrat transfers their form ( form) to bureaucrat .
Bureaucrat transfers their form ( form) back to bureaucrat .
Bureaucrat attempts to transfer forms ( forms) to bureaucrat .
Bureaucrat receives a new form .
Bureaucrat receives a new form .
Bureaucrat transfers all their forms ( forms) to bureaucrat .
Example 1
Example 2