/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) と B=(B_1,B_2,\ldots,B_N) が与えられます．
あなたは，次の 2 種類の操作を好きな順序で何度でも行うことができます．
- A のすべての要素に 1 を加える．
- 1\leq i\leq N を満たす整数 i を 1 つ選び，A_i を -A_i に置き換える．
A と B を多重集合として一致させることができるか判定してください．可能な場合は，必要な操作回数の最小値も求めてください． ここで，多重集合として一致するとは，どの整数についても，A に含まれる個数と B に含まれる個数が等しいことをいいます．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\leq T\leq 10^4
- 1\leq N\leq 100
- -10^9\leq A_i,B_i\leq 10^9 (1 \leq i \leq N)
- 1 つの入力に含まれるテストケースについて，N^3 の総和は 10^6 以下である．
- 入力はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる．
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
出力
T 行出力せよ．
i 行目には，i 番目のテストケースにおいて，A と B を多重集合として一致させることができない場合は -1 を，できる場合は必要な操作回数の最小値を出力せよ．
入力例 1
8 4 -3 -1 0 2 -2 1 2 3 2 0 0 0 1 1 0 0 1 0 3 1 3 1 2 1 3 -3 1 3 -1 -1 -1 1 1 1 6 -4 -2 -2 0 1 3 -3 -1 0 2 2 4
出力例 1
2 -1 0 3 4 1 2 5
1 番目のテストケースでは，まず A_2 の符号を反転し，次にすべての要素に 1 を加えると，A=(-2,2,1,3) となります． これで B と多重集合として一致します．1 回の操作では一致させることができないので，必要な操作回数の最小値は 2 です．
2 番目のテストケースでは，どのような操作を行っても B=(0,1) と多重集合として一致させることはできません．
Score : 800 points
Problem Statement
You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
You can perform the following two types of operations any number of times in any order.
- Add 1 to every element of A.
- Choose an integer i satisfying 1\leq i\leq N, and replace A_i with -A_i.
Determine whether it is possible to make A and B equal as multisets. If it is possible, also find the minimum number of operations required. Here, A and B are equal as multisets when, for every integer, the number of its occurrences in A equals the number of its occurrences in B.
You are given T test cases; find the answer for each of them.
Constraints
- 1\leq T\leq 10^4
- 1\leq N\leq 100
- -10^9\leq A_i,B_i\leq 10^9 (1 \leq i \leq N)
- The sum of N^3 over all test cases in a single input is at most 10^6.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
Output T lines.
The i-th line should contain -1 if it is impossible to make A and B equal as multisets in the i-th test case, and otherwise the minimum number of operations required.
Sample Input 1
8 4 -3 -1 0 2 -2 1 2 3 2 0 0 0 1 1 0 0 1 0 3 1 3 1 2 1 3 -3 1 3 -1 -1 -1 1 1 1 6 -4 -2 -2 0 1 3 -3 -1 0 2 2 4
Sample Output 1
2 -1 0 3 4 1 2 5
In the first test case, first negate A_2, then add 1 to every element, which makes A=(-2,2,1,3). Now A and B are equal as multisets. They cannot be made equal with one operation, so the minimum number of operations required is 2.
In the second test case, no matter how you perform the operations, A cannot be made equal to B=(0,1) as multisets.