시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 0 0 0 0.000%

문제

The Association of Chartered Mountaineers oversaw a sharp resurgence in membership this year, and must now face the inevitable strains of growth: the group photo they usually take can no longer fit everyone in one long row.

Members have been split into two groups: Tall and Short, so that the picture can be doubled up with taller people standing behind shorter people in two rows of n/2 each.

Every cloud has a silver lining, especially when mountaineering. This is an opportunity for the members to meet people. Many new joiners. were assigned a mentor from the members who had already signed up before they joined; the organisation wants to choose a way of arranging the rows such that nobody is standing directly in front of or behind their mentor, assuming they have one.

Find a way of arranging the two rows such that this is possible. The number of tall people is always the same as the number of short people.

입력

The input consists of:

  • a line consisting of the number of members in the mountaineering society, which is a positive even integer m (1 ≤ m ≤ 105).
  • m further lines, with the ith line (1 ≤ i ≤ m) consisting of an integer indicating whether the ith member is short (0) or tall (1), then the number of the ith member’s mentor, ti (0 ≤ t ≤ m). When ti = i, this indicates that the ith member did not have a mentor.

출력

If an arrangement is possible, output 2 lines of n/2 numbers each to show which member should stand where.

Every number of type 1 should occur somewhere on the first row, and every number of type 0 should occur somewhere on the second row. Nobody should share a column with their mentor.

Otherwise, output impossible.

예제 입력 1

4
0 1
1 1
1 2
0 3

예제 출력 1

3 2
1 4

예제 입력 2

4
0 1
1 1
0 1
1 1

예제 출력 2

impossible

예제 입력 3

10
0 1
1 1
1 1
1 1
0 1
0 4
0 6
1 1
0 7
1 2

예제 출력 3

10 8 3 2 4
1 6 7 9 5