{"problem":{"name":"Non-Adjacent Flip","description":{"content":"We have $N$ coins numbered $1$ to $N$ with two distinguishable sides. A string $S$ represents the current state of the coins. If the $i$\\-th character of $S$ is `1`, coin $i$ is showing heads; if that","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc156_a"},"statements":[{"statement_type":"Markdown","content":"We have $N$ coins numbered $1$ to $N$ with two distinguishable sides. A string $S$ represents the current state of the coins. If the $i$\\-th character of $S$ is `1`, coin $i$ is showing heads; if that character is `0`, coin $i$ is showing tails.\nYou can repeat the following operation zero or more times.\n\n*   Choose a pair of integers $(i,j)$ such that $1\\leq i < j\\leq N$ and $j-i\\geq \\bm{2}$. Flip coin $i$ and coin $j$.\n\nDetermine whether it is possible to make all the $N$ coins show tails. If it is possible, find the minimum number of operations needed.\nYou are given $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 2\\times 10^5$\n*   $3 \\leq N \\leq 2\\times 10^5$\n*   $S$ is a string of length $N$ consisting of `0` and `1`.\n*   All numbers in the input are integers.\n*   For each input file, the sum of $N$ over the test cases is at most $2\\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\n​ Each case is in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc156_a","tags":[],"sample_group":[["5\n3\n101\n6\n101101\n5\n11111\n6\n000000\n30\n111011100110101100101000000111","1\n2\n-1\n0\n8\n\nFor the first test case, you can perform the operation with $(i,j)=(1,3)$ to make all the coins show tails in one operation.\nFor the second test case, you can perform the operation with $(i,j)=(1,3)$ and then with $(i,j)=(4,6)$ to make all the coins show tails in two operations.\nFor the third test case, you can prove that there is no way to make all the coins show tails, so you should print `-1`.\nFor the fourth test case, the coins already show tails, so no operation is needed."]],"created_at":"2026-03-03 11:01:14"}}