← 返回题目列表

Codeforces · 1361/C

C. 约翰尼和梅根的项链

中文机器翻译题面 查看原题

约翰尼的妹妹梅根最近过生日。她哥哥给她买了一个盒子,上面写着“你漂亮的项链——你自己做吧!”。它包含许多项链部件和一些魔术胶。

项链部分是连接两颗珍珠的链条。每颗珍珠的颜色可以由非负整数定义。神奇的胶水可以让梅根将两颗珍珠(可能来自同一个项链部分)合并为一颗。颜色 $$$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$$$。

下图显示了这种结构。