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 $ が存在する**ことが制約によって保証されている．

入力は以下の形式で標準入力から与えられる． > $ 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!) $ をこの順に空白区切りで出力せよ．

### 部分点 - $ N = 1, 2, 3, 4, 5, 6 $ を満たすデータセットに正解した場合は，それぞれ $ 1, 2, 4, 8, 16, 69 $ 点が与えられる． ### Sample Explanation 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))) $ などが成り立つことが確認できる． ### Constraints - $ 1 \le N \le 6 $ ． - $ 1 \le A(i, j) \le N! $ ( $ 1 \le i, j \le N! $ )． - 問題文の条件を満たす $ q $ が存在する．