CF1361C Johnny and Megan's Necklace

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](https://en.wikipedia.org/wiki/Exclusive_or#Computer_science) 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!

N/A

N/A

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.