URI Online Judge | 1562

Choosing the Pairs

By Gabriel Dalalio, ITA Brazil

Timelimit: 3

A teacher wants to split all the students in pairs to realize a school work. When this happens, there is a lot of fighting between students to choose the work partner, because many students want to choose the best students in the class.

This time, the teacher decided to choose the pairs in a different way. Each student will choose a partner and tell the teacher. After this, the teacher will choose the pairs so that all pairs meet at least the option of one student in the pair.

Now I think you already know what is your work on this problem. Given the option list of the students, print the list of pairs the teacher should choose.

Input

The input consists of several test cases. Each test case consists of two lines. The first line of a test case contains an integer N (2 ≤ N ≤ 10000) equal to the number of students in the classroom. The second line contains the wishes of all students in order (the person chosen by the student 1, by the student 2, etc). No student will choose himself.

Output

For each test, the output consists of one line. If it is impossible to form the pairs satisfying the rule chosen by the teacher, print "IMPOSSIBLE". If there is a solution, print the partners of each student in order (student 1 partner, student 2 partner, etc). If there is more than one solution, you must prioritize the option of students with small identification number, which means, whenever possible you must meet the option of the student 1, then try to meet the option of the student 2, and so on. Remember that we are choosing pairs, if the partner of the student X is equal to Y, then the partner of the student Y should be X.

In the last case of the samples, the pairs are (1,3), satisfying the student 1 option, and (2,4), satisfying the student 4 option.

 Sample Input Sample Output 2 2 1 3 2 3 1 4 3 1 4 2 2 1 IMPOSSIBLE 3 4 1 2