AT_xmascon23_g Group Structure

设 $N$ 为正整数。所有 $(1, 2, \ldots, N)$ 的全排列记作 $\mathfrak{S}_N$。对于 $f \in \mathfrak{S}_N$，可以将其视为序列 $(f(1), f(2), \ldots, f(N))$。对于 $f, g \in \mathfrak{S}_N$，定义 $f \circ g \in \mathfrak{S}_N$，对于 $k = 1, 2, \ldots, N$，有 $(f \circ g)(k) = f(g(k))$。将 $\mathfrak{S}_N$ 的所有元素按字典序排列为 $P(1) < P(2) < \cdots < P(N!)$。 给定 $(N!)^2$ 个整数 $A(i, j)$ （$1 \le i, j \le N!$）。求出所有满足下列条件的 $(1, 2, \ldots, N!)$ 的一个排列 $q = (q(1), q(2), \ldots, q(N!))$，使得对于所有 $1 \le i, j \le N!$，有 $P(q(i)) \circ P(q(j)) = P(q(A(i, j)))$，并将所有满足条件的 $q$ **按字典序输出**。 此外，**已由题目保证存在满足条件的 $q$**。

输入按以下格式从标准输入中给出。 > $N$ $A(1, 1)$ $A(1, 2)$ $\cdots$ $A(1, N!)$ $A(2, 1)$ $A(2, 2)$ $\cdots$ $A(2, N!)$ $\vdots$ $A(N!, 1)$ $A(N!, 2)$ $\cdots$ $A(N!, N!)$

第 $1$ 行输出满足条件的 $q$ 的个数。 接下来每一行按**字典序**依次输出满足条件的 $q$，每行依次输出 $q(1), q(2), \ldots, q(N!)$，用空格分隔。

### 部分得分 - 对于满足 $N = 1, 2, 3, 4, 5, 6$ 的数据集，分别可以获得 $1, 2, 4, 8, 16, 69$ 分。 ### 样例解释 1 $\mathfrak{S}_3$ 的元素如下 $6$ 个： - $P(1) = (1, 2, 3)$ - $P(2) = (1, 3, 2)$ - $P(3) = (2, 1, 3)$ - $P(4) = (2, 3, 1)$ - $P(5) = (3, 1, 2)$ - $P(6) = (3, 2, 1)$ 例如当 $q = (3, 2, 6, 4, 5, 1)$ 时， - $P(q(1)) = (2, 1, 3)$ - $P(q(2)) = (1, 3, 2)$ - $P(q(3)) = (3, 2, 1)$ - $P(q(4)) = (2, 3, 1)$ - $P(q(5)) = (3, 1, 2)$ - $P(q(6)) = (1, 2, 3)$ 此时可以确认 $P(q(2)) \circ P(q(3)) = P(q(4)) = P(q(A(2, 3)))$ 等式成立。 ### 数据范围 - $1 \le N \le 6$。 - $1 \le A(i, j) \le N!$（$1 \le i, j \le N!$）。 - 已保证存在满足条件的 $q$。 由 ChatGPT 5 翻译