{"problem":{"name":"Valid Output for DSU Problems","description":{"content":"A sequence that can be obtained as $A$ by performing the following operations is called a **special sequence**: *   Prepare an undirected graph consisting of $N$ vertices and $0$ edges, and a sequenc","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc074_d"},"statements":[{"statement_type":"Markdown","content":"A sequence that can be obtained as $A$ by performing the following operations is called a **special sequence**:\n\n*   Prepare an undirected graph consisting of $N$ vertices and $0$ edges, and a sequence $A$ of length $0$.\n*   Prepare queries for integers $i,j$ satisfying $1 \\leq i < j \\leq N$ and $q \\in {1,2}$:\n\n*   When $q=1$, connect vertices $i$ and $j$ with an edge.\n*   When $q=2$, append $1$ to the end of $A$ if vertices $i$ and $j$ are connected, and append $0$ otherwise.\n\n*   There are $N(N-1)$ possible queries; rearrange them in any order and process them in that order.\n\nYou are given a sequence $B$ of length $\\frac{N(N-1)}{2}$ consisting of $0$ and $1$. You can perform the following operation on $B$ any number of times:\n\n*   Choose an integer $i$ satisfying $1 \\leq i \\leq \\frac{N(N-1)}{2}-1$, and swap $B_i$ and $B_{i+1}$.\n\nDetermine whether it is possible to make $B$ a special sequence, and if possible, find the minimum number of operations required.\nSolve $T$ test cases per input.\n\n## Constraints\n\n*   $1 \\leq T$\n*   $2 \\leq N \\leq 500$\n*   $|B| =\\frac{N(N-1)}{2}$\n*   $0 \\leq B_i \\leq 1$\n*   The sum of $|B|$ over all test cases is at most $3 \\times 10^5$.\n*   The sum of $N^3$ over all test cases is at most $500^3$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is given in the following format:\n\n$N$  \n$B_1$ $B_2$ $\\ldots$ $B_{\\frac{N(N-1)}{2}}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc074_d","tags":[],"sample_group":[["4\n4\n1 1 0 1 1 0\n2\n1\n3\n0 0 0\n5\n1 1 1 1 1 1 1 1 1 0","1\n0\n0\n3\n\nIn the first test case, if the queries are processed in the order $(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)$, the resulting sequence is $(1,1,0,1,0,1)$, and $B$ can be changed to this sequence by performing the operation once. Also, $(1,1,0,1,1,0)$ is not a special sequence, so the answer is $1$."]],"created_at":"2026-03-03 11:01:13"}}