最后,你击败了 Razor,现在你是头号通缉街头赛车手。克罗斯警官已派出全部警力追捕你。幸运的是,你找到了一个藏身之处,但你担心克罗斯和他的部队最终会找到你。为了增加您的生存机会,您需要调整并重新喷漆您的 BMW M3 GTR。
这辆车可以被想象成一个排列的 $$$n$$$ 维超立方体。一个简单的 $$$n$$$ 维超立方体是递归构建的无向无权图,如下所示:
- 取两个简单的$$$(n-1)$$$维超立方体,其中一个的顶点编号从$$$0$$$到$$$2^{n-1}-1$$$,另一个的顶点编号从$$$2^{n-1}$$$到$$$2^{n}-1$$$。一个简单的 $$$0$$$ 维超立方体只是一个顶点。
- 对于每个 $$$0\leq i < 2^{n-1}$$$,在顶点 $$$i$$$ 和 $$$i+2^{n-1}$$$ 之间添加一条边。
排列的 $$$n$$$ 维超立方体是通过以任意方式排列简单 $$$n$$$ 维超立方体的顶点编号而形成的。
下面给出了简单和置换 $$$3$$$ 维超立方体的示例:
请注意,排列 $$$n$$$ 维超立方体具有以下属性:
- 正好有 $$$2^n$$$ 个顶点。
- 正好有 $$$n\cdot 2^{n-1}$$$ 边。
- 每个顶点都恰好连接到 $$$n$$$ 个其他顶点。
- 没有自环或重复边。
让我们用 $$$P$$$ 表示用于从简单的 $$$n$$$ 维超立方体生成代表您的汽车的排列 $$$n$$$ 维超立方体的排列。在搞乱汽车的功能之前,您需要找到这种排列,以便在出现问题时可以恢复汽车。但工作还没有完成。
您有 $$$n$$$ 不同颜色,编号从 $$$0$$$ 到 $$$n-1$$$。您希望为这个排列 $$$n$$$ 维超立方体的顶点着色,使得对于满足 $$$0\leq u < 2^n$$$ 的每个顶点 $$$u$$$ 以及满足 $$$0\leq c < n$$$ 的每个颜色 $$$c$$$,至少有一个与 $$$u$$$ 相邻的顶点 $$$v$$$ 有一种颜色$$$c$$$。换句话说,从每个顶点,只要移动到相邻顶点,就必须能够到达任何颜色的顶点。
给定排列的 $$$n$$$ 维超立方体,找到任何有效的排列 $$$P$$$ 和着色。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 4096$$$) — 测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 16$$$)。
接下来的 $$$n\cdot 2^{n-1}$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$0\leq u, v < 2^n$$$) 表示编号为 $$$u$$$ 和 $$$v$$$ 的顶点之间有一条边。
保证输入中描述的图是排列的 $$$n$$$ 维超立方体。
此外,保证所有测试用例的 $$$2^n$$$ 总和不超过 $$$2^{16}=65\,536$$$。
输出
对于每个测试用例,打印两行。
在第一行中,输出长度为 $$$2^n$$$ 的任何排列 $$$P$$$,可用于将简单的 $$$n$$$ 维超立方体转换为输入中给出的排列 $$$n$$$ 维超立方体。如果两个置换超立方体具有相同的边集,则它们被认为是相同的。如果有多个答案,则输出其中任何一个。
在第二行中,打印颜色。如果没有办法对满足条件的顶点着色,则输出$$$-1$$$。否则,输出包含 $$$2^n$$$ 空格分隔整数的单行。第 $$$i$$$ 个整数必须是排列的 $$$n$$$ 维超立方体中编号为 $$$(i-1)$$$ 的顶点的颜色。如果有多个答案,则输出其中任何一个。
示例
输入 #1
3 1 0 1 2 0 1 1 2 2 3 3 0 3 0 1 0 5 0 7 1 2 1 4 2 5 2 6 3 5 3 6 3 7 4 6 4 7
输出 #1
0 1 0 0 0 1 3 2 0 0 1 1 5 3 0 7 2 6 1 4 -1
注意
第一个测试用例的着色和排列超立方体如下所示:
第二个测试用例的着色和排列超立方体如下所示:
问题陈述中给出了第三个测试用例的排列超立方体。然而,可以证明,没有办法为满足所有条件的立方体着色。请注意,其他一些排列如 $$$[0, 5, 7, 3, 1, 2, 4, 6]$$$ 和 $$$[0, 1, 5, 2, 7, 4, 3, 6]$$$ 也将给出相同的排列超立方体。