题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIII Olimpiada Informatyczna — III etap Klubowicze

拜托尼亚讨论俱乐部堪称独一无二。俱乐部拥有 $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$ 个整数，表示圆桌上成员的正确座位顺序，数字间以单个空格分隔。

若存在多个正确答案，输出任意一个即可。

3
0 5
4 1
3 6
7 2

0 5 7 2 6 3 1 4

提示

附加样例

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$）。