Magical Permutation
Contest: Codeforces Round 558 (Div. 2)
Difficulty rating: 2400
Tags: bitmasks, brute force, constructive algorithms, data structures, graphs, math

Kuro has just learned about permutations and he is really excited to create a new permutation type. He has chosen $$$n$$$ distinct positive integers and put all of them in a set $$$S$$$. Now he defines a magical permutation to be:

- A permutation of integers from $$$0$$$ to $$$2^x - 1$$$, where $$$x$$$ is a non-negative integer.
- The bitwise xor of any two consecutive elements in the permutation is an element in $$$S$$$.

Since Kuro is really excited about magical permutations, he wants to create the longest magical permutation possible. In other words, he wants to find the largest non-negative integer $$$x$$$ such that there is a magical permutation of integers from $$$0$$$ to $$$2^x - 1$$$. Since he is a newbie in the subject, he wants you to help him find this value of $$$x$$$ and also the magical permutation for that $$$x$$$.

Input format:
The first line contains the integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of elements in the set $$$S$$$.

The next line contains $$$n$$$ distinct integers $$$S_1, S_2, \ldots, S_n$$$ ($$$1 \leq S_i \leq 2 \cdot 10^5$$$) — the elements in the set $$$S$$$.

Output format:
In the first line print the largest non-negative integer $$$x$$$, such that there is a magical permutation of integers from $$$0$$$ to $$$2^x - 1$$$.

Then print $$$2^x$$$ integers describing a magical permutation of integers from $$$0$$$ to $$$2^x - 1$$$. If there are multiple such magical permutations, print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$0, 1, 3, 2$$$ is a magical permutation since:

- $$$0 \oplus 1 = 1 \in S$$$
- $$$1 \oplus 3 = 2 \in S$$$
- $$$3 \oplus 2 = 1 \in S$$$

Where $$$\oplus$$$ denotes bitwise xor operation.

Example input:
3
1 2 3

Example output:
2
0 1 3 2

Example input:
2
2 3

Example output:
2
0 2 1 3

Editorial:
The idea here is iterate $$$x$$$ and check if it is possible to create a magical permutation for the current $$$x$$$ we are iterating through.
An observation to be made is that if it is possible to create a magical permutation $$$P$$$ from $$$0$$$ to $$$2^x - 1$$$, then it must be possible to express each integer from $$$0$$$ to $$$2^x - 1$$$ as the xor value of elements in one subset of $$$S$$$. This is because $$$0$$$ is represented as the xor value of the empty subset of $$$S$$$. Because of that, every element to the left of $$$0$$$ in $$$P$$$ is also the xor value of one subset of $$$S$$$, and so is every element to the right of $$$0$$$ in $$$P$$$.
Because of that, we first check that if we can create every integer from $$$0$$$ to $$$2^x - 1$$$ using only the xor values of every subset of $$$S$$$. This is possible by creating a basis for integers from $$$0$$$ to $$$2^x - 1$$$ — $$$x$$$ integers such that each integer from $$$0$$$ to $$$2^x - 1$$$ is the xor value of a subset of these $$$x$$$ integers — from $$$S$$$ using Gaussian elimination.
Now, if it is possible to create such a basis for integers from $$$0$$$ to $$$2^x - 1$$$ using only elements of $$$S$$$, is it possible to create a magic permutation then? Recall that each integer from $$$0$$$ to $$$2^x - 1$$$ corresponds to the xor value of a subset of the basis, or in other words, corresponds to a bitmask of the basis. We can also narrow down the original condition, such that the xor value of any two consecutive elements belongs to the basis; or in other words, the corresponding bitmask of any two consecutive elements in the magical permutation differs by exactly 1 bit. The problem now becomes creating a permutation of integers from $$$0$$$ to $$$2^x - 1$$$ such that any two consecutive elements in this permutation differs by 1 bit, and then convert this permutation to a magical permutation using the created basis. It turns out that we can always do this using Gray codes, although DFS works just as well.
It also turns out that the basis for integers from $$$0$$$ to $$$2^x - 1$$$ does not exceed $$$2^x - 1$$$, we can sort $$$S$$$ and create the basis along with checking the aforementioned condition.
Complexity: $$$O(n \log n + n \log MAX + MAX)$$$ if Gray codes are used, or $$$O(n \log n + n \log MAX + MAX \log MAX)$$$ is DFS is used instead, where $$$MAX$$$ denotes the maximum value of elements in $$$S$$$.