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$ 是连通的，则在 $A$ 末尾追加 $1$，否则追加 $0$。 - $N(N-1)$ 个可能的操作可以任意排列顺序，并按顺序依次处理。 现给定一个长度为 $\frac{N(N-1)}{2}$ 仅包含 $0$ 和 $1$ 的序列 $B$，你可以对 $B$ 执行如下操作任意多次： - 选择一个满足 $1 \leq i \leq \frac{N(N-1)}{2}-1$ 的整数 $i$，交换 $B_i$ 和 $B_{i+1}$。 请判断能否通过若干次操作使 $B$ 变为一个特殊序列。如果可以，输出所需操作的最小次数；否则输出 $-1$。 对每个输入的测试用例，求解上述问题。

从标准输入读入，格式如下： > $T$ $case_1$ $case_2$ $…$ $case_T$ 每个测试用例格式如下： > $N$ $B_1$ $B_2$ $…$ $B_{\frac{N(N-1)}{2}}$

共输出 $T$ 行。第 $t$ 行输出 $B$ 变为特殊序列所需的最小操作次数；如果无法做到，输出 $-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,0,1,1,0)$ 不是特殊序列，所以答案为 $1$。 ### 数据范围 - $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$。 - 输入均为整数。 由 ChatGPT 5 翻译