## IPSC 2001

## Problem H – Magic

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.

### FAQ

- Is the assistant an extraterrestrial or someone practicing telepathy? No, she is a normal, albeit
beautiful, human being.
- How did the assistant get out of the mirror box? By magic, of course.
- Can the assistant see through the mirror box or pockets? Obviously not, see answer to Q. #1.

### Input file specification

Given is odd **N**, the number of cards.

### Output file specification

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`".

### Example

**Input file:**
3

**Output file** (one out of several possible):

1 2 -> 2
1 3 -> 1
2 3 -> 3

### Acknowledgments

Thanks to Tom Hayes for bringing this nice and magic idea to our attention.