P12745 [POI 2016 R3] 俱乐部成员 Club members

翻译来自于 [LibreOJ](https://loj.ac/p/5041)。

**题目译自 [XXIII Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi23-3/dashboard/) [Klubowicze](https://szkopul.edu.pl/problemset/problem/3Kqkgeapr-W-MBprNjUDGICL/statement/)** 拜托尼亚讨论俱乐部堪称独一无二。俱乐部拥有 $2^n$ 名成员，每位成员都对 $n$ 个基本问题表达了观点。这些问题的具体表述并不重要，只需知道每个问题有两种回答选项。每位成员的观点可用一个二进制位串编码，转换为十进制后为 $0$ 至 $2^n-1$ 的整数。 俱乐部中没有两位成员观点完全相同。若两位成员的观点仅在一个问题上不同，则称他们**几乎一致**。此外，俱乐部由 $2^{n-1}$ 名男士和 $2^{n-1}$ 名女士组成，配对形成 $2^{n-1}$ 对情侣。成员们围坐在圆桌上，需安排座位，使得每位成员旁坐着自己的伴侣，并且另一侧的邻座是与其**几乎一致**的人。

第一行包含一个整数 $n$，表示基本问题的数量。 接下来的 $2^{n-1}$ 行描述成员情侣对，第 $i$ 行包含两个整数 $a_i, b_i$ $(0 \leq a_i, b_i \leq 2^n-1)$，表示观点为 $a_i$ 和 $b_i$ 的成员是一对情侣。每位成员的观点编号在输入中恰好出现一次。

若不存在满足条件的座位安排，输出一行一个字符串 `NIE`。 若存在满足条件的座位安排，输出一行，包含 $2^n$ 个整数，表示圆桌上成员的正确座位顺序，数字间以单个空格分隔。 若存在多个正确答案，输出任意一个即可。

**附加样例** 1. $n=4$，若 $i$ 为偶数，则编号 $i$ 和 $i+1$ 的成员为情侣。 2. $n=10$，若 $i$ 为奇数，则编号 $i$ 和 $i+1$ 的成员为情侣，例外是编号 $2^n-1$ 与编号 $0$ 配对。 3. $n=15$，随机样例，输入的情侣对按 $a_i$ 升序排列。 测试数据分为 $18$ 组，每组 $5$ 或 $6$ 分。第 $k$ $(1\leq k\leq 18)$ 组仅包含 $n=k+1$ 的测试（即 $2 \leq n \leq 19$）。