Secret Santa Draw

You are given a list of n participants in a Secret Santa event and the pairings from last year. Your task is to generate a new valid Secret Santa drawing such that:

• No one gifts to themselves, i.e. for every participant p, the assigned receiver r must satisfy $$p \neq r$$.
• No one gifts to the same person as last year. If last year \(p\) gifted to \(q\), then this year \(p\) must not gift to \(q\), i.e. $$r \neq \text{lastYear}(p)$$.

Find one valid assignment meeting the above constraints. It is guaranteed that a solution exists for the given input.

inputFormat

The input is read from standard input (stdin) and has the following format:

n
name1 name2 ... name_n
giver1 receiver1
giver2 receiver2
...
giver_n receiver_n

Where:

• n is an integer representing the number of participants.
• The second line contains n space-separated names.
• The next n lines each contain two names. Each line represents last year's Secret Santa pairing: the first name is the giver, and the second name is the receiver.

outputFormat

Output to standard output (stdout) n lines. Each line should contain a pairing in the format:

giver receiver

The ordering of the output should follow the order of the participants (as given in the input) for the giver.

## sample

3
Alice Bob Charlie
Alice Bob
Bob Charlie
Charlie Alice

Alice Charlie
Bob Alice
Charlie Bob

</p>