Gift Exchange

In this problem, you are given a list of names representing participants in a gift exchange. Your task is to generate a valid gift exchange assignment such that no participant is assigned their own name. Formally, given a list of names \( N = \{n_1, n_2, \ldots, n_k\} \), you need to produce a permutation \( P \) of these names such that for all \( i \), \( P(i) \neq n_i \).

Note: Each participant gives exactly one gift and receives exactly one gift. The solution must generate a valid assignment when reading input from standard input (stdin) and output the results to standard output (stdout).

inputFormat

The first line contains an integer \( n \) (with \( n \ge 2 \)), representing the number of participants. The second line contains \( n \) names separated by spaces.

outputFormat

For each participant (in the order of input), output a line with two names separated by a space: the giver and the receiver. The assignment must ensure that no person is paired with themselves.

4
Alice Bob Charlie Diana

Alice Charlie
Bob Diana
Charlie Bob
Diana Alice