#include "bits/stdc++.h"
using namespace std;
#include "debug.h"
void solve() {
int n, m;
cin >> n >> m;
if (!m || (n - m) % 2) {
cout << -1 << '\n';
return;
}
vector<int> a(n), ord;
for (int i = 0; i < m; i++) {
int x;
cin >> x;
x--;
ord.push_back(x);
a[x] = 1;
}
std::sort(ord.begin(), ord.end());
ord.push_back(n);
vector<map<int, int>> dp(m + 1);
if (ord[0] % 2 == 1) {
dp[0][1] = -1;
} else if (!ord[0]) {
dp[0][0] = -1;
} else {
dp[0][2] = -1;
}
for (int i = 1; i <= m; i++) {
int len = ord[i] - ord[i - 1] - 1;
for (auto [v, _] : dp[i - 1]) {
if (len < v) {
continue;
}
if ((len - v) % 2 == 1) {
dp[i][1] = v;
} else if (len == v) {
dp[i][0] = v;
} else if (v) {
dp[i][0] = v;
dp[i][2] = v;
} else {
dp[i][2] = v;
}
}
}
// debug(dp);
if (dp[m].find(0) == dp[m].end()) {
cout << -1 << '\n';
return;
}
vector<int> ans, ans2, tmp, used(n), kek(n);
{
int j = 0;
for (int i = m - 1; i >= 0; i--) {
j = dp[i + 1][j];
kek[ord[i]] = j;
}
}
// debug(kek);
for (int i = 0; i < n; ) {
if (a[i] == 1) {
i++;
continue;
}
int j = i;
while (j < n && a[j] == 0) {
j++;
}
int rem = 0;
if (i && a[i - 1] == 1) {
rem += kek[i - 1];
}
if (j < n && a[j] == 1) {
rem += kek[j];
}
// debug(rem);
if (j - i < rem) {
cout << -1 << '\n';
return;
}
for (int v = i; v < j; v++) {
tmp.push_back(v);
}
while ((int) tmp.size() > rem) {
if ((int) tmp.size() < 3) {
cout << -1 << '\n';
return;
}
ans.push_back(tmp.end()[-2]);
used[tmp.end()[-1]] = used[tmp.end()[-3]] = 1;
tmp.pop_back();
tmp.pop_back();
tmp.pop_back();
tmp.push_back(ans.back());
}
tmp.clear();
i = j;
}
int want = 0;
for (int i = 0; i < n; i++) {
if (used[i]) {
continue;
}
if (a[i] == 1) {
if (want) {
cout << -1 << '\n';
return;
}
want = (int) tmp.size();
tmp.clear();
for (int j = 0; j < want; j++) {
ans.push_back(i);
}
} else {
if (want) {
want--;
} else {
tmp.push_back(i);
}
}
}
if (!tmp.empty() || want) {
cout << -1 << '\n';
return;
}
cout << (int) ans.size() << '\n';
for (auto& i : ans) {
cout << i + 1 << " ";
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Compilation message
del13.cpp:5:10: fatal error: debug.h: No such file or directory
5 | #include "debug.h"
| ^~~~~~~~~
compilation terminated.
