A famous magician enters the stage, followed by a beautiful assistant. He starts his show by pulling several hares from his magic hat, then he finds a bouquet of flowers in the assistant's scarf, and finally he locks the assistant in a seemingly empty mirror box. And then comes the audience's turn. The magician shows them a deck of N cards (all the cards are different, N is odd). A volunteer comes to the stage and selects (N+1)/2 cards. The rest of the cards is lost forever in the magician's hat. After waving his hands above the selected cards, the magician picks up one of the cards and gives it to the volunteer who shows it to the audience and subsequently hides it in his pocket. The assistant, after being released from the mirror box, comes to the deck of the remaining (N+1)/2-1 cards. She waves her hands above it for a while and then she describes the one card hidden in the volunteer's pocket.
How could this happen? Magic? A clever trick? Given N, find an algorithm (if it exists) for the magician and his assistant.
Given is odd N, the number of cards.
Let's assume that the cards are numbered 1,2,...,N. In the output file, list all possible subsets of {1,2,...,N} of size (N+1)/2, every subset on a separate line. Every subset S is followed by "->" and by a number c from S. The number c is the one card that the magician should give to the volunteer. This describes the magician's algorithm. The assistant has to be able to find the unique c, after seeing the set S-{c}. Therefore, in no two lines S-{c} can be the same. If this holds, assistant can use the "reversed magician's algorithm" to identify the correct c. (Both of them have to memorize your output file.) Every two consecutive numbers in S, the number c and "->" are separated by single spaces. If no algorithm exists, output a single word "MAGIC".
3
Output file (one out of several possible):
1 2 -> 2 1 3 -> 1 2 3 -> 3
Thanks to Tom Hayes for bringing this nice and magic idea to our attention.