Screenshot from "Prisoner of Benda" episode of Futurama
This was suggested by Radovan Marcus, thanks a lot!
One of episodes of Futurama series is about Professor inventing personality-swapping machine - if two people use it, then their minds are exchanged and they can have fun wandering around in other one's body. However it soon appears, if people want to exchange back, machine woudn't work for the same pair of bodies.
This makes problem of returning personalities to their bodies somewhat complicated. It seems, however, that in general case it could be solved if we use two additional persons temporarily.
Problem Statement
We are given a set of several people, denoted with letters starting with A. They have exchanged personalities and we know
the sequence of exchanges, like A-B, D-C etc (here letters refer to bodies, i.e. bodies A and B exchange
personalities they contain, whatever these personalities are).
To return all their personalities to the proper bodies we
now need another sequence of exchanges and (most probably) we need two additional people,
(let's call them X and Y) temporarily.
As a result, every person should have his/her "self" back in his/her own body. Don't forget X and Y of course
- don't leave them swapped :)
Input and Output
Input data will contain number of people N and number of swaps S in the first line. (and N is always
small enough so that people "names" won't reach X and Y)
Next line describes swap order - each consisting of two letters separated with dash;
swapping pairs themselves are separated by space.
Answer should have another sequence of personality swaps in the same format. There should be no same swaps
in both sequences, and as result all personalities should be restored to respective bodies!
Example:
input data:
4 2
A-B C-D
answer:
B-D A-C D-A C-B
Note: supposing, that people's "souls" (i.e. personalities) are labeled with small letters a b c d (while
capital letters mark the bodies), we have, after first sequence of swaps (given as input) situation described by
A:b B:a C:d D:c. The next 4 swaps from the answer allow us to return to
A:a B:b C:c D:d, even without using X and Y persons (but it was just luck).