AT_agc074_d [AGC074D] Valid Output for DSU Problems

以下の操作を行った結果 $ A $ として得られる可能性がある数列を**特別な数列**と呼ぶことにします。 - $ N $ 頂点 $ 0 $ 辺からなる無向グラフと長さ $ 0 $ の数列 $ A $ を用意する。 - $ 1 \leq i < j \leq N $ を満たす整数 $ i,j $ と $ q \in \{1,2\} $ に対し、以下のクエリを用意する。 - $ q=1 $ のとき、頂点 $ i $ と頂点 $ j $ を辺で結ぶ。 - $ q=2 $ のとき、頂点 $ i $ と頂点 $ j $ が連結であるならば $ 1 $ を、連結でないならば $ 0 $ を、 $ A $ の末尾に追加する。 - 考えられるクエリは $ N(N-1) $ 通りあるが、これらを好きな順に並べ替え、その順に処理する。 $ 0 $ と $ 1 $ からなる長さ $ \frac{N(N-1)}{2} $ の数列 $ B $ が与えられます。 $ B $ に対して以下の操作を何回でも行うことができます。 - $ 1 \leq i \leq \frac{N(N-1)}{2}-1 $ を満たす整数 $ i $ を選び、 $ B_i $ と $ B_{i+1} $ を入れ替える。 $ B $ を特別な数列にすることが可能かを判定し、可能ならばそのために必要な操作回数の最小値を求めてください。 $ 1 $ つの入力につき、 $ T $ 個のテストケースを解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_{\frac{N(N-1)}{2}} $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースについて $ B $ を特別な数列にすることが可能ならばそのために必要な操作回数の最小値を、不可能ならば `-1` を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、 $ (q,i,j)=(1,1,4), $ $ (2,1,4), $ $ (1,2,4), $ $ (2,1,2), $ $ (1,1,2), $ $ (2,2,3), $ $ (2,2,4), $ $ (2,3,4), $ $ (1,3,4), $ $ (1,1,3), $ $ (2,1,3), $ $ (1,2,3) $ の順にクエリを処理すると、得られる数列は $ (1,1,0,1,0,1) $ となり、 $ B $ に $ 1 $ 回の操作を行うことでこの数列に変えることができます。また、 $ (1,1,0,1,1,0) $ は特別な数列ではないため、答えは $ 1 $ になります。 ### Constraints - $ 1 \leq T $ - $ 2 \leq N \leq 500 $ - $ |B| =\frac{N(N-1)}{2} $ - $ 0 \leq B_i \leq 1 $ - 全てのテストケースにおける $ |B| $ の総和は $ 3 \times 10^5 $ 以下 - 全てのテストケースにおける $ N^3 $ の総和は $ 500^3 $ 以下 - 入力される値は全て整数