题目描述

特许登山者协会今年的会员人数大幅增加，过去把所有人排成一长排拍摄合影的方式已经无法容纳全部成员。

协会将成员分成“高个”和“矮个”两组，高个成员站在矮个成员后方，组成两排，每排恰有 $m/2$ 人。高个成员与矮个成员的人数始终相同。

许多新成员加入协会时，会由比自己更早入会的成员担任导师。协会希望安排两排的站位，使任何成员都不会与自己的导师站在同一列，也就是不会恰好站在导师的正前方或正后方。

请构造一种满足要求的两排排列；若不存在合法排列，则判断无解。

输入格式

输入包含：

• 第一行包含一个正偶数 $m$（$1\le m\le10^5$），表示协会成员数量。
• 接下来 $m$ 行，第 $i$ 行包含两个整数：
  • 第一个整数为 $0$ 或 $1$，表示第 $i$ 名成员是矮个（$0$）还是高个（$1$）；
  • 第二个整数为 $t_i$（$0\le t_i\le m$），表示第 $i$ 名成员的导师编号。

当 $t_i=i$ 时，表示第 $i$ 名成员没有导师。

输出格式

若存在合法排列，输出两行，每行包含 $m/2$ 个成员编号：

• 第一行必须恰好包含所有高个成员；
• 第二行必须恰好包含所有矮个成员；
• 两行中位于同一位置的两名成员不能互为导师与学生。

成员在各自行中的顺序可以任意，只要满足上述要求。

若不存在合法排列，输出：

impossible

样例 1

输入：
4
0 1
1 1
1 2
0 3

输出：
3 2
1 4

样例 2

输入：
4
0 1
1 1
0 1
1 1

输出：
impossible

样例 3

输入：
10
0 1
1 1
1 1
1 1
0 1
0 4
0 6
1 1
0 7
1 2

输出：
10 8 3 2 4
1 6 7 9 5