CF1543E.The Final Pursuit

Finally, you have defeated Razor and now, you are the Most Wanted street racer. Sergeant Cross has sent the full police force after you in a deadly pursuit. Fortunately, you have found a hiding spot but you fear that Cross and his force will eventually find you. To increase your chances of survival, you want to tune and repaint your BMW M3 GTR.

The car can be imagined as a permuted $n$-dimensional hypercube. A simple $n$-dimensional hypercube is an undirected unweighted graph built recursively as follows:

• Take two simple $(n-1)$-dimensional hypercubes one having vertices numbered from $0$ to $2^{n-1}-1$ and the other having vertices numbered from $2^{n-1}$ to $2^{n}-1$. A simple $0$-dimensional Hypercube is just a single vertex.
• Add an edge between the vertices $i$ and $i+2^{n-1}$ for each $0\leq i \lt 2^{n-1}$.

A permuted $n$-dimensional hypercube is formed by permuting the vertex numbers of a simple $n$-dimensional hypercube in any arbitrary manner.

Examples of a simple and permuted $3$-dimensional hypercubes are given below:

Note that a permuted $n$-dimensional hypercube has the following properties:

• There are exactly $2^n$ vertices.
• There are exactly $n\cdot 2^{n-1}$ edges.
• Each vertex is connected to exactly $n$ other vertices.
• There are no self-loops or duplicate edges.

Let's denote the permutation used to generate the permuted $n$-dimensional hypercube, representing your car, from a simple $n$-dimensional hypercube by $P$. Before messing up the functionalities of the car, you want to find this permutation so that you can restore the car if anything goes wrong. But the job isn't done yet.

You have $n$ different colours numbered from $0$ to $n-1$. You want to colour the vertices of this permuted $n$-dimensional hypercube in such a way that for each and every vertex $u$ satisfying $0\leq u \lt 2^n$ and for each and every colour $c$ satisfying $0\leq c \lt n$, there is at least one vertex $v$ adjacent to $u$ having a colour $c$. In other words, from each and every vertex, it must be possible to reach a vertex of any colour by just moving to an adjacent vertex.

Given the permuted $n$-dimensional hypercube, find any valid permutation $P$ and colouring.

最后，你击败了Razor，如今已成为最臭名昭著的街头赛车手。克罗斯警长已派出全部警力对你展开致命追捕。幸运的是，你找到了一处藏身之所，但你担心克罗斯及其部下终将找到你。为了提高生存几率，你打算对你的宝马M3 GTR进行调校与重新喷漆。

这辆汽车可被建模为一个置换后的 $n$ 维超立方体（permuted $n$-dimensional hypercube）。一个标准的 $n$ 维超立方体（simple $n$-dimensional hypercube） 是一个无向无权图，其递归构造方式如下：

• 取两个标准的 $(n-1)$ 维超立方体：其中一个的顶点编号为 $0$ 到 $2^{n-1}-1$，另一个的顶点编号为 $2^{n-1}$ 到 $2^{n}-1$；而一个标准的 $0$ 维超立方体仅包含单个顶点。
• 对每个满足 $0\leq i < 2^{n-1}$ 的 $i$，在顶点 $i$ 与顶点 $i+2^{n-1}$ 之间添加一条边。

一个置换后的 $n$ 维超立方体，则是通过对标准 $n$ 维超立方体的所有顶点编号施加任意一个置换（permutation）得到的。

下面给出了一个标准的和一个置换后的 $3$ 维超立方体的示例：

注意：一个置换后的 $n$ 维超立方体具有以下性质：

• 恰好含有 $2^n$ 个顶点；
• 恰好含有 $n\cdot 2^{n-1}$ 条边；
• 每个顶点恰好与 $n$ 个其他顶点相邻；
• 图中不含自环（self-loops）或重边（duplicate edges）。

记将标准 $n$ 维超立方体变换为表示你座驾的该置换后 $n$ 维超立方体所用的顶点置换为 $P$。在贸然改动车辆功能之前，你希望先找出这一置换 $P$，以便万一发生故障时能及时恢复车辆原状。但任务尚未完成。

你手头有 $n$ 种不同的颜色，编号为 $0$ 至 $n-1$。你需要对这个置换后的 $n$ 维超立方体的顶点进行染色，使得：对每个顶点 $u$（满足 $0\leq u < 2^n$）以及每种颜色 $c$（满足 $0\leq c < n$），均存在至少一个与 $u$ 相邻的顶点 $v$，其颜色恰为 $c$。换言之，从任意顶点出发，仅通过移动至一个相邻顶点，就必须能够到达任意一种颜色的顶点。

给定该置换后的 $n$ 维超立方体，请找出任意一组有效的置换 $P$ 和顶点染色方案。

The first line of input contains a single integer $t$ ($1\leq t\leq 4096$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($1\leq n\leq 16$).

Each of the next $n\cdot 2^{n-1}$ lines contain two integers $u$ and $v$ ($0\leq u, v \lt 2^n$) denoting that there is an edge between the vertices numbered $u$ and $v$.

It is guaranteed that the graph described in the input is a permuted $n$-dimensional hypercube.

Additionally, it is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{16}=65\,536$.

输入的第一行包含一个整数 $t$（$1\leq t\leq 4096$），表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$1\leq n\leq 16$）。

接下来的 $n\cdot 2^{n-1}$ 行中，每行包含两个整数 $u$ 和 $v$（$0\leq u, v \lt 2^n$），表示编号为 $u$ 和 $v$ 的顶点之间存在一条边。

保证输入所描述的图是一个经过顶点重标号（permutation）的 $n$ 维超立方体（hypercube）。

此外，保证所有测试用例中 $2^n$ 的总和不超过 $2^{16}=65\,536$。

For each test case, print two lines.

In the first line, output any permutation $P$ of length $2^n$ that can be used to transform a simple $n$-dimensional hypercube to the permuted $n$-dimensional hypercube given in the input. Two permuted hypercubes are considered the same if they have the same set of edges. If there are multiple answers, output any of them.

In the second line, print the colouring. If there is no way to colour the vertices satisfying the conditions, output $-1$. Otherwise, output a single line containing $2^n$ space separated integers. The $i$-th integer must be the colour of the vertex numbered $(i-1)$ in the permuted $n$-dimensional hypercube. If there are multiple answers, output any of them.

对每个测试用例，输出两行。

第一行，输出任意一个长度为 $2^n$ 的排列 $P$，该排列可用于将一个简单的 $n$ 维超立方体变换为输入中给定的置换后的 $n$ 维超立方体。若两个置换后的超立方体具有相同的边集，则认为它们是相同的。若存在多个答案，输出其中任意一个即可。

第二行，输出顶点的着色方案。若不存在满足条件的顶点着色方案，则输出 $-1$；否则，输出一行包含 $2^n$ 个以空格分隔的整数。其中第 $i$ 个整数表示在置换后的 $n$ 维超立方体中编号为 $(i-1)$ 的顶点的颜色。若存在多个答案，输出其中任意一个即可。

The colouring and the permuted hypercube for the first test case is shown below:

The colouring and the permuted hypercube for the second test case is shown below:

The permuted hypercube for the third test case is given in the problem statement. However, it can be shown that there exists no way to colour that cube satifying all the conditions. Note that some other permutations like $[0, 5, 7, 3, 1, 2, 4, 6]$ and $[0, 1, 5, 2, 7, 4, 3, 6]$ will also give the same permuted hypercube.

第一个测试用例的着色方案及置换超立方体如下所示：

第二个测试用例的着色方案及置换超立方体如下所示：

第三个测试用例的置换超立方体已在题目陈述中给出。然而，可以证明：不存在满足所有条件的对该立方体的着色方案。注意，其他一些置换（例如 $[0, 5, 7, 3, 1, 2, 4, 6]$ 和 $[0, 1, 5, 2, 7, 4, 3, 6]$）也会生成相同的置换超立方体。