P7946 「Wdcfr-1」Yet Another Cirno Game (hard version)

**两个版本之间的唯一区别是你是否需要找到一种方法来获得最大分数。** Cirno 画了一张图。这张图由 $4\cdot n$ 个节点组成，节点编号为 $0$ 到 $4\cdot n - 1$。此外： - 对于 $0\le i\le 3$ 和 $0 \le j, k < n$，节点 $(n\cdot i + j)$ 和节点 $(n\cdot i + k)$ 是相连的。 - 对于 $0 \le i \le n$ 和 $0 \le j, k \le 3$，节点 $(i + n\cdot j)$ 和节点 $(i + n\cdot k)$ 是相连的。 Cirno 叫来了 Daiyousei 和她一起玩。 游戏规则如下： - 首先，Cirno 选择 $2\cdot n$（即一半）的节点，并将它们涂成蓝色。其余的节点保持红色。 - 然后有 $2\cdot n$ 轮：每轮 Cirno 首先选择一个蓝色节点，Daiyousei 选择一个红色节点。如果这两个节点是相连的，Daiyousei 得到一分。 试图最大化 Daiyousei 能得到的分数。

第一行给出 $n$。 第二行跟随 $n$ 个数字：它们是 Cirno 选择的节点。

第一行输出 $x$，即 Daiyousei 能得到的最大分数。 然后输出 $2\cdot n$ 个整数。对于 Cirno 选择的每个节点，输出 Daiyousei 对应选择的节点。显然，选择的节点顺序无关紧要。解必须获得可能的最大分数。

### 解释 在下图中，矩阵中的节点是相互连接的。Cirno 选择了节点 $0,1,2,3,4,5$。 下面的箭头显示了 Daiyousei 获得她能得到的最大分数的一种可能方式。  ### 约束 $1\le n\le 2\times 10^6$。 题面翻译由 ChatGPT-4o 提供。