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 翻译