题目描述

The only difference between the two versions is whether you have to find a way to get the maximum points.

Cirno drew a graph. This graph consists of $4\cdot n$ nodes, which are numbered $0$ through $4\cdot n - 1$. Also:

• For $0\le i\le 3$ and $0 \le j, k \lt n$, node $(n\cdot i + j)$ and node $(n\cdot i + k)$ are connected.
• For $0 \le i \le n$ and $0 \le j, k \le 3$, node $(i + n\cdot j)$ and node $(i + n\cdot k)$ are connected.

Cirno called Daiyousei to come and play with her.

The rules for this game are as follows:

• Firstly, Cirno chooses $2\cdot n$ (i.e. half) of the nodes, and she colors them blue. The rest are left red.
• Then there are $2\cdot n$ turns: for each turn Cirno first chooses a blue node, and Daiyousei chooses a red node. If those two nodes are connected, Daiyousei gets a point.

Try to maximize the number of points Daiyousei gets.

输入格式

In the first line, $n$ is provided.

In the second line, $n$ numbers follow: they are the nodes that Cirno chose.

输出格式

In the first line output $x$, which is the maximum number of points Daiyousei can get.

Then output $2\cdot n$ integers. For each node that Cirno chooses, output the corresponding node that Daiyousei responds with. Obviously the order of the chosen nodes doesn't matter. The solution must get the maximum number of points possible.

题目大意

两个难度之间的唯一区别为是否需要输出对应的匹配方案

给定 $4n$ 个点，点的编号从 $0$ 到 $4n-1$。每个点有两种属性 $x$ 和 $y$，编号为 $i$ 的点的属性为 $x_i=\left\lfloor\frac{i}{n}\right\rfloor,y_i=i-n\left\lfloor\frac{i}{n}\right\rfloor$。对于每两个点 $i,j(0\le i <j < 4n)$ 之间，若 $x_i=x_j$ 或 $y_i= y_j$，则这两点有一条无向边相连。现有其中 $2n$ 个不同的点被选择，试给每个被选择的点都匹配上另一个点，使得：

• 被匹配到的点未被选择；
• 每个点都只被匹配一次；
• 若每个点与其匹配的点之间有连边，那么记为一分，需要最大化分值。

请输出最大的分值和对应的匹配方案。

3
0 1 2 3 4 5

6
6 7 8 9 10 11

提示

Explanation

In the following picture, nodes in matrices are connected to each other. Cirno chose nodes $0,1,2,3,4,5$.

Arrows below show a possible way for Daiyousei to get the maximum number of points she can get.

Constraints

$1\le n\le 2\times 10^6$.