Johnny and Megan's Necklace
Contest: Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!
Difficulty rating: 2500
Tags: binary search, bitmasks, constructive algorithms, dfs and similar, dsu, graphs

Johnny's younger sister Megan had a birthday recently. Her brother has bought her a box signed as "Your beautiful necklace — do it yourself!". It contains many necklace parts and some magic glue.

The necklace part is a chain connecting two pearls. Color of each pearl can be defined by a non-negative integer. The magic glue allows Megan to merge two pearls (possibly from the same necklace part) into one. The beauty of a connection of pearls in colors $$$u$$$ and $$$v$$$ is defined as follows: let $$$2^k$$$ be the greatest power of two dividing $$$u \oplus v$$$ — exclusive or of $$$u$$$ and $$$v$$$. Then the beauty equals $$$k$$$. If $$$u = v$$$, you may assume that beauty is equal to $$$20$$$.

Each pearl can be combined with another at most once. Merging two parts of a necklace connects them. Using the glue multiple times, Megan can finally build the necklace, which is a cycle made from connected necklace parts (so every pearl in the necklace is combined with precisely one other pearl in it). The beauty of such a necklace is the minimum beauty of a single connection in it. The girl wants to use all available necklace parts to build exactly one necklace consisting of all of them with the largest possible beauty. Help her!

Input format:
The first line contains $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$ — the number of necklace parts in the box. Each of the next $$$n$$$ lines contains two integers $$$a$$$ and $$$b$$$ $$$(0 \leq a, b < 2^{20})$$$, which denote colors of pearls presented in the necklace parts. Pearls in the $$$i$$$-th line have indices $$$2i - 1$$$ and $$$2i$$$ respectively.

Output format:
The first line should contain a single integer $$$b$$$ denoting the maximum possible beauty of a necklace built from all given parts.

The following line should contain $$$2n$$$ distinct integers $$$p_i$$$ $$$(1 \leq p_i \leq 2n)$$$ — the indices of initial pearls in the order in which they appear on a cycle. Indices of pearls belonging to the same necklace part have to appear at neighboring positions in this permutation (so $$$1\,4\,3\,2$$$ is not a valid output, whereas $$$2\,1\,4\,3$$$ and $$$4\,3\,1\,2$$$ are). If there are many possible answers, you can print any.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example the following pairs of pearls are combined: $$$(7, 9)$$$, $$$(10, 5)$$$, $$$(6, 1)$$$, $$$(2, 3)$$$ and $$$(4, 8)$$$. The beauties of connections equal correspondingly: $$$3$$$, $$$3$$$, $$$3$$$, $$$20$$$, $$$20$$$.

The following drawing shows this construction.

Example input:
5
13 11
11 1
3 5
17 1
9 27

Example output:
3
8 7 9 10 5 6 1 2 3 4

Example input:
5
13 11
11 1
3 5
17 1
7 29

Example output:
2
8 7 10 9 5 6 4 3 2 1

Editorial:
Say that we want to check if it is possible to construct a necklace with beauty at least $$$b$$$. To this end, we will construct a graph of $$$2^{b}$$$ vertices. For a necklace part with pearls in colors $$$u$$$ and $$$v$$$ there will be an edge in this graph between vertices with zero-based indices $$$v\text{ & }(2^b-1)$$$ and $$$u\text{ & }(2^b-1)$$$. In a necklace with beauty (at least) $$$b$$$, only pearl with colors having last $$$b$$$ bits the same can be glued together. Note that this is the exact condition that the edge endpoints have to satisfy to be in the same vertex. Since all the necklace parts have to be used, a necklace of beauty at least $$$b$$$ is an Euler cycle of this graph.
The solution will construct the graph mentioned above for all possible values of $$$b$$$ (we can iterate over all of them since there are only $$$21$$$ of them). If the constructed graph is Eulerian, it is possible to achieve the current value of $$$b$$$.
In order to find a sample necklace with the optimal beauty, one has to find the Euler cycle in the graph corresponding to the optimal value.
Challenge: In another version of this task you are not allowed to glue pearls of the same color together. There is also a guarantee that there are no three pearls of the same color. Time complexity of the solution is the same.