T183640 止战之殇（2021 CoE III D）

> 孩子们眼中的希望 是什么形状 > 是否醒来有面包当早餐 再喝碗热汤 > 农夫被烧毁土地跟村庄 终于拿起枪 > 她却慢慢习惯放弃了抵抗 > 孩子们眼中的希望 是什么形状 > 是否院子有秋千可以荡 口袋里有糖 > 刺刀的光被仇恨所擦亮 在远方野蛮 > 而她却微笑着不知道慌张 > ——《止战之殇》

有 $n$ 个因为战争而历尽苦难的孩子，他们想要终止野蛮的战争。他们每人要选定一个整数作为自己的 **天真值**，第 $i$ 个孩子的 **天真值** 为 $a_i$，**天真值** 可以为负数。然后他们每次会选择两个孩子 $x,y$ 一起进行一次值为正整数 $k$ 的 **祈祷**，直到每人都进行了 $n-1$ 次 **祈祷**。一次由两个 **天真值** 分别为 $a_x$ 和 $a_y$ 的孩子一起进行一次值为 $k$ 的 **祈祷** 能够产生两个值分别为 $a_x+k$ 和 $a_y+k$ 的 **殇歌**。显然进行完所有 **祈祷** 后会产生 $n(n-1)$ 个 **殇歌**。如果这些 **殇歌** 的值 **恰好** 为 $1$ 到 $n(n-1)$ 的正整数 **各一个**，那么整个过程为一次 **止战之殇**，可以终止血腥的战争。现在孩子们想要知道他们怎样选择自己的 **天真值** 和每次 **祈祷** 的值才能制造出 **止战之殇**，由于他们还太小，所以就请你帮助他们。 #### 题意简述 给定 $n$，构造一个长度为 $n$ 的整数列 $a_1,\ a_2,\ \dots,\ a_n$ 与 $\dfrac{n(n-1)}{2}$ 个整数三元组 $(x_i,\ y_i,\ k_i)，x_i \neq y_i, \ k_i \in \mathbb{Z_+}$，使得 $\forall j \in \{1,\ 2,\ \dots,\ n\}$，均有 $$\sum_{i=1}^{\frac{n(n-1)}{2}}((x_i=j) + (y_i=j))=n-1$$ 且 $\left\{c \ | \ c =a_{x_i}+k_i, \ i=1,2,\cdots,\frac{n(n-1)}{2}\right\}\cup\left\{d \ | \ d =a_{y_i}+k_i, \ i=1,2,\cdots,\frac{n(n-1)}{2}\right\}=\{1,2,\cdots,n(n-1)\}$。

一行 $3$ 个整数 $n,\ op_1,\ op_2$。 如果 $op_1=1$，那么必须满足每一对 $1 \le x

如果有解，第一行输出 $n$，否则输出 $-1$。 如果有解，第二行输出 $n$ 个非负整数表示编号为 $1$ 到 $n$ 的孩子分别的 **天真值**，接下来 $\dfrac{n(n-1)}{2}$ 行每行输出第 $i$ 次 **祈祷** 选定的 $x_i,\ y_i,\ k_i$。

#### 样例解释 对于第一组样例，最后没有生成任何 **殇歌**，满足要求。 对于第二组样例，$0+2=2,-1+2=1$，恰好为 $1$ 到 $2$ 各一个。 对于第三组样例，可以发现没有满足条件的方法。 对于第四组样例，有 $$5+7=12,0+7=7,5+1=6,3+1=4,2+7=9,3+7=10,$$ $$2+6=8,5+6=11,3+2=5,0+2=2,0+1=1,2+1=3,$$ 恰好为 $1$ 到 $12$ 各一个。 ------------ #### 数据范围 本题共有 $20$ 个数据点，每个数据点 $5$ 分，各个数据点的数据范围与限制如下。 | Testdata No. | $n \le$ | $op_1$ | $op_2$ | 特殊限制 | | :-: | :-: | :-: | :-: | :-: | | $1 \sim 4$ | $300$ | $0$ | $1$ | $n$ 为偶数 | | $5 \sim 10$ | $300$ | $0$ | $1$ | $n$ 为奇数 | | $11 \sim 17$ | $3 \times 10^3$ | $1$ | $1$ | 无 | | $18 \sim 20$ | $7$ | $0$ | $0$ | 无 | 对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^3$，$op_1,op_2 \in \{0,1\}$。 ------------ #### 提示 本题提供 [$\texttt{Special Judge}$ 源码](https://www.luogu.com.cn/paste/h4pwri6z) 和 `checker.exe`，使用方法为: 命令行在目标文件夹输入指令： ``` checker.exe input.txt output.txt output.txt ``` 其中 `input.txt` 是输入数据文件，`output.txt` 是程序运行结果文件。观察评判结果即可。 - `Accepted.` 表示答案正确。 - `ax equals to ay.` 表示 $a_x$ 与 $a_y$ 相等。 - `Misjudgment of the existence of the answer.` 表示有解性判断不正确。 - `Negative ai.` 表示 $a_i$ 为负数（$op2=1$ 时）。 - `Invalid (x,y,k) No.i.` 表示 $x_i$ 或 $y_i$ 不在 $[1,n]$ 中或 $x_i=y_i$ 或 $k_i$ 不为正整数。 - `Invalid sum No.i.` 表示 $a_{x_i}+k_i$ 或 $a_{y_i}+k_i$ 不在 $[1,n(n-1)]$ 中。 - `Sum No.i already appeared.` 表示 $a_{x_i}+k_i$ 或 $a_{y_i}+k_i$ 已经出现过。 - `(x,y) No.i already appeared.` 表示 $(x_i,y_i)$ 已经出现过（$op_1=1$ 时）。 - `x/y No.i appeared more than n-1 times.` 表示 $x_i$ 或 $y_i$ 出现了超过 $n-1$ 次。 **请务必保证输出格式正确**，否则 $\texttt{Special Judge}$ 可能会返回 $\texttt{Unknown Error}$ 等不可预估的结果。