约翰尼的妹妹梅根最近过生日。她哥哥给她买了一个盒子,上面写着“你漂亮的项链——你自己做吧!”。它包含许多项链部件和一些魔术胶。
项链部分是连接两颗珍珠的链条。每颗珍珠的颜色可以由非负整数定义。神奇的胶水可以让梅根将两颗珍珠(可能来自同一个项链部分)合并为一颗。颜色 $$$u$$$ 和 $$$v$$$ 珍珠连接的美丽定义如下:令 $$$2^k$$$ 为 $$$u \oplus v$$$ 的二除法的最大幂 — $$$u$$$ 和 $$$v$$$ 的异或。那么美丽就等于$$$k$$$。如果$$$u = v$$$,你可以假设美丽等于$$$20$$$。
每颗珍珠最多可以与另一颗珍珠组合一次。将项链的两个部分合并将它们连接起来。梅根多次使用胶水,最终可以制作出这条项链,这是一个由连接的项链部件制成的循环(因此项链中的每一颗珍珠都与其中的另一颗珍珠精确地结合在一起)。这样一条项链的美在于其中单个连接的最低限度的美。女孩想使用所有可用的项链部件来制作一条项链,该项链由所有部件组成,并且尽可能美观。帮助她!
输入
第一行包含 $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$ — 盒子中项链部件的数量。接下来的 $$$n$$$ 行包含两个整数 $$$a$$$ 和 $$$b$$$ $$$(0 \leq a, b < 2^{20})$$$,表示项链部分中珍珠的颜色。第 $$$i$$$ 行中的珍珠分别具有索引 $$$2i - 1$$$ 和 $$$2i$$$。
输出
第一行应包含一个整数 $$$b$$$ 表示由所有给定部件构建的项链的最大可能美观度。
以下行应包含 $$$2n$$$ 不同的整数 $$$p_i$$$ $$$(1 \leq p_i \leq 2n)$$$ - 初始珍珠的索引,按照它们在循环中出现的顺序排列。属于同一项链部分的珍珠索引必须出现在该排列中的相邻位置(因此 $$$1\,4\,3\,2$$$ 不是有效输出,而 $$$2\,1\,4\,3$$$ 和 $$$4\,3\,1\,2$$$ 是有效输出)。如果有很多可能的答案,您可以打印任何一个。
示例
输入 #1
5 13 11 11 1 3 5 17 1 9 27
输出 #1
3 8 7 9 10 5 6 1 2 3 4
输入 #2
5 13 11 11 1 3 5 17 1 7 29
输出 #2
2 8 7 10 9 5 6 4 3 2 1
输入 #3
1 1 1
输出 #3
20 2 1
注意
在第一个示例中,组合了以下珍珠对:$$$(7, 9)$$$、$$$(10, 5)$$$、$$$(6, 1)$$$、$$$(2, 3)$$$ 和 $$$(4, 8)$$$。连接之美相应地相同:$$$3$$$、$$$3$$$、$$$3$$$、$$$20$$$、$$$20$$$。
下图显示了这种结构。