A16563 | $XOR-convenience (Hard Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是此问题的困难版本。不同版本之间的区别在于，在此版本中，$1 \le i \le n-1$。请注意，困难版本的正确解不一定是简单版本的正确解。 给定一个正整数 $n$。求一个长度为 $n$ 的排列 $ ^{\text{∗}} $ $p$，使得对于每个 $i$（$1 \le i \le n-1$），都存在一个 $j$（$i \le j \le n$）使得 $^\text{†}$ $p_i = p_j \oplus i$，或者判断这样的排列不存在。 $ ^{\text{∗}} $ 长度为 $n$ 的排列是一个包含从 $1$ 到 $n$ 的 $n$ 个不同整数的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。 † $\oplus$ 表示按位异或操作。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。测试用例的描述如下。 每个测试用例只有一行，包含一个正整数 $n$（$3 \leq n \leq 2 \times 10^5$）——排列的长度。 保证所有测试用例的 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，如果存在合适的排列，则输出 $n$ 个整数 $p_1, p_2, \ldots, p_n$ —— 排列 $p$。否则输出 $-1$。 如果存在多个解，输出其中任意一个。

输入 #1

2
3
4

输出 #1

2 1 3
-1

C++ 编辑器

输入

输出