配点 : 100 点
布谷鸟「因为给出了对称群的乘法表,请将其对应到排列上」
布谷鸟「因为下标太小而不便于读写,请允许使用括号」
問題文
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 存在这一点由约束保证。
制約
- 1 \le N \le 6.
- 1 \le A(i, j) \le N! (1 \le i, j \le N!).
- 满足题目条件的 q 存在。
部分点
- N = 1, 2, 3, 4, 5, 6 若数据集正确,则各自 1, 2, 4, 8, 16, 69 点。 如果所有满足
入力
输入是按以下格式从标准输入给出的。
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 该值应乘以按字典顺序 1 行,每行 q(1), q(2), \ldots, q(N!) 按这个顺序以空格分隔输出。
入力例 1
3 6 4 5 2 3 1 5 6 4 3 1 2 4 5 6 1 2 3 3 1 2 5 6 4 2 3 1 6 4 5 1 2 3 4 5 6
出力例 1
6 2 3 6 5 4 1 2 6 3 4 5 1 3 2 6 4 5 1 3 6 2 5 4 1 6 2 3 5 4 1 6 3 2 4 5 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))) 等得以确认成立。