問題ヴィジュアル

クリックをすると, 問題ヴィジュアルが表示されます.

問題文

$27$ 個の要素を持つ $3 \times 3 \times 3$ の $3$ 重添字数列 $A = \left(A_{i,j,k} \right)_{\substack{1 \leq i \leq 3 \\ 1 \leq j \leq 3 \\ 1 \leq k \leq 3}}$ が与えられる.

$A$ が以下の条件を全て満たすとき, $A$ は「満開列」であるという.

• $1 \leq j \leq 3, 1 \leq k \leq 3$ を満たす任意の整数の組 $(j,k)$ に対して, $A_{1,j,k} + A_{2,j,k} + A_{3,j,k} = X_{j,k}$ である.
• $1 \leq i \leq 3, 1 \leq k \leq 3$ を満たす任意の整数の組 $(i,k)$ に対して, $A_{i,1,k} + A_{i,2,k} + A_{i,3,k} = Y_{i,k}$ である.
• $1 \leq i \leq 3, 1 \leq j \leq 3$ を満たす任意の整数の組 $(i,j)$ に対して, $A_{i,j,1} + A_{i,j,2} + A_{i,j,3} = Z_{i,j}$ である.

$A$ に対して, 以下の操作 (S) を $0$ 回以上行うことによって, $A$ を満開列にすることは可能か? そして, 可能ならば $A$ を満開列にするために必要になる操作 (S) を行う最小回数を求めよ.

• 操作 (S): 以下の $3$ 個の操作から $1$ つを選び, 実行する.
  • $1 \leq p_1 < p_2 \leq 3$ を満たす整数の組 $(p_1, p_2)$ を $1$ つ選び, 以下を実行する.
    • $1 \leq j \leq 3, 1 \leq k \leq 3$ を満たす整数の組 $(j,k)$ それぞれに対して, 次の操作を $1$ 回ずつ行う: $A_{p_1, j, k}$ と $A_{p_2,j,k}$ を入れ替える.
  • $1 \leq q_1 < q_2 \leq 3$ を満たす整数の組 $(q_1, q_2)$ を $1$ つ選び, 以下を実行する.
    • $1 \leq i \leq 3, 1 \leq k \leq 3$ を満たす整数の組 $(i,k)$ それぞれに対して, 次の操作を $1$ 回ずつ行う: $A_{i, q_1, k}$ と $A_{i,q_2,k}$ を入れ替える.
  • $1 \leq r_1 < r_2 \leq 3$ を満たす整数の組 $(r_1, r_2)$ を $1$ つ選び, 以下を実行する.
    • $1 \leq i \leq 3, 1 \leq j \leq 3$ を満たす整数の組 $(i,j)$ それぞれに対して, 次の操作を $1$ 回ずつ行う: $A_{i, j, r_1}$ と $A_{i,j,r_2}$ を入れ替える.

ここで, $1$ 以上 $3$ 以下の整数 $i_1, i_2, j_1, j_2, k_1, k_2$ に対して, 「$A_{i_1,j_1,k_1}$ と $A_{i_2,j_2,k_2}$ を入れ替える」とは, $A$ に対して以下の変更を行うこととする.

• まず, 変数 $x_1, x_2$ を用意する. 次に, $x_1$ に $A_{i_1,j_1,k_1}$ を, $x_2$ に $A_{i_2,j_2,k_2}$ を代入する. その後, $A_{i_1,j_1,k_1}$ に $x_2$ を, $A_{i_2,j_2,k_2}$ に $x_1$ を代入する.

$T$ 個のテストケースについて答えよ.

制約

• $1 \leq T \leq 5000$.
• 各テストケース毎の制約
  • $-10^8 \leq A_{i,j,k} \leq 10^8 \quad (1 \leq i \leq 3, 1 \leq j \leq 3, 1 \leq k \leq 3)$.
  • $-3 \times 10^8 \leq X_{j,k} \leq 3 \times 10^8 \quad (1 \leq j \leq 3, 1 \leq k \leq 3)$.
  • $-3 \times 10^8 \leq Y_{i,k} \leq 3 \times 10^8 \quad (1 \leq i \leq 3, 1 \leq k \leq 3)$.
  • $-3 \times 10^8 \leq Z_{i,j} \leq 3 \times 10^8 \quad (1 \leq i \leq 3, 1 \leq j \leq 3)$.
• 入力は全て整数である.

入力

$T$
$\textrm{Testcase}_1$
$\textrm{Testcase}_2$
$\vdots$
$\textrm{Testcase}_T$

各テストケースは以下の形式で与えられる.

$A_{1,1,1}$ $A_{1,1,2}$ $A_{1,1,3}$
$A_{1,2,1}$ $A_{1,2,2}$ $A_{1,2,3}$
$A_{1,3,1}$ $A_{1,3,2}$ $A_{1,3,3}$
$A_{2,1,1}$ $A_{2,1,2}$ $A_{2,1,3}$
$A_{2,2,1}$ $A_{2,2,2}$ $A_{2,2,3}$
$A_{2,3,1}$ $A_{2,3,2}$ $A_{2,3,3}$
$A_{3,1,1}$ $A_{3,1,2}$ $A_{3,1,3}$
$A_{3,2,1}$ $A_{3,2,2}$ $A_{3,2,3}$
$A_{3,3,1}$ $A_{3,3,2}$ $A_{3,3,3}$
$X_{1,1}$ $X_{1,2}$ $X_{1,3}$
$X_{2,1}$ $X_{2,2}$ $X_{2,3}$
$X_{3,1}$ $X_{3,2}$ $X_{3,3}$
$Y_{1,1}$ $Y_{1,2}$ $Y_{1,3}$
$Y_{2,1}$ $Y_{2,2}$ $Y_{2,3}$
$Y_{3,1}$ $Y_{3,2}$ $Y_{3,3}$
$Z_{1,1}$ $Z_{1,2}$ $Z_{1,3}$
$Z_{2,1}$ $Z_{2,2}$ $Z_{2,3}$
$Z_{3,1}$ $Z_{3,2}$ $Z_{3,3}$

出力

出力は $T$ 行からなる.

第 $t~(1 \leq t \leq T)$ 行目には, 第 $t$ テストケースについて, $A$ を満開列にすることが可能であるならば, 満開列にするために必要になる操作 (S) を行う最小回数を, 不可能ならば, -1 を出力せよ.

最後に改行を忘れないこと.

サンプル

3
1 0 1
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
1 0 1
0 0 0
0 0 0
1 0 1
0 0 0
0 0 0
0 0 2
1 2 3
4 5 6
7 8 9
-1 -2 -3
-4 -5 -6
-7 -8 -9
1 2 3
4 5 6
7 8 9
100 200 300
400 500 600
700 800 900
100 200 300
400 500 600
700 800 900
100 200 300
400 500 600
700 800 900
19970104 19981114 19980215
20010129 19990417 20000418
19991012 20021219 20020323
19981021 20010829 20020112
19991013 20010710 20000102
20050927 20020113 20060109
20040725 20050707 20050412
20030217 20061108 20060509
20040818 20050215 20050122
60062235 60031359 60061029
60091547 60082757 60130554
60042650 59991850 60050739
59992750 59971245 60000956
60162030 60111760 60161043
60041652 60022961 60080323
60000964 60032554 59931433
60151834 60141155 60141844
60001825 60131149 60011962

2
-1
4