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 翻译