CF1956C Nene's Magical Matrix

魔法少女 Nene 有一个 $n\times n$ 的矩阵 $a$，初始时所有元素均为零。矩阵 $a$ 的第 $i$ 行第 $j$ 列的元素记作 $a_{i, j}$。 她可以对这个矩阵进行以下两种操作： - 类型 $1$ 操作：选择一个 $1$ 到 $n$ 之间的整数 $i$，以及一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$。同时将 $a_{i, j}:=p_j$，对所有 $1 \le j \le n$。 - 类型 $2$ 操作：选择一个 $1$ 到 $n$ 之间的整数 $i$，以及一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$。同时将 $a_{j, i}:=p_j$，对所有 $1 \le j \le n$。 Nene 想要最大化矩阵中所有数字的和 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$。她希望你帮她找到一种操作方案，使得这个和最大。由于她不想操作次数太多，你需要给出一个不超过 $2n$ 次操作的方案。 长度为 $n$ 的排列是指包含 $1$ 到 $n$ 的 $n$ 个互不相同整数的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$ 但出现了 $4$）。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。 每组测试用例的唯一一行包含一个整数 $n$（$1 \le n \le 500$），表示矩阵 $a$ 的大小。 保证所有测试用例中 $n^2$ 的和不超过 $5 \cdot 10^5$。

对于每组测试用例，第一行输出两个整数 $s$ 和 $m$（$0\leq m\leq 2n$），分别表示矩阵中数字的最大和，以及你方案中的操作次数。 接下来的 $m$ 行，每行描述一次操作，格式如下： - 一个整数 $c$（$c \in \{1, 2\}$），表示操作类型； - 一个整数 $i$（$1 \le i \le n$），表示操作作用的行或列编号； - 一个排列 $p_1, p_2, \ldots, p_n$，表示本次操作使用的排列。 注意，你不需要最小化操作次数，只需保证操作次数不超过 $2n$。可以证明，最大可能的和总能在不超过 $2n$ 次操作内实现。

在第一个测试用例中，最大和 $s=1$，可以通过 $1$ 次操作 $a_{1, 1}:=1$ 实现。 在第二个测试用例中，最大和 $s=7$，可以通过如下 $3$ 次操作实现：  可以证明，无法使矩阵中数字的和超过 $7$。 由 ChatGPT 4.1 翻译