//#pragma GCC optimize("Ofast,unroll-loops")//
//#pragma GCC target("fma,avx")//,avx2,fma")
//#pragma GCC optimization ("O3")
/*#pragma GCC optimization ("unroll-loops")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
*/
#include <bits/stdc++.h>
using namespace std;
//typedef long long int;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int t;
int vis[200001];
int dp[200001][3];
int back[200001][3];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
if(q==0){
cout<<-1<<endl;
continue;
}
for(int i=0;i<n;i++){
vis[i]=0;
}
//vector<int> aa;
set<int> ac;
for(int i=0;i<q;i++){
int bb;
cin>>bb;
bb--;
vis[bb]=1;
//aa.pb(bb);
ac.insert(bb);
}
if(q==n){
cout<<0<<endl;
cout<<endl;
continue;
}
vector<vector<deque<int>>> ss;
int cot=0;
int stt=0;
for(int i=0;i<n;i++){
if(vis[i]==0){
// cout<<i<<"::"<<endl;
if(cot>=2 or stt==0){
deque<int> tt;
tt.pb(i);
ss.pb({tt});
}
else if(cot==0){
ss[ss.size()-1][ss[ss.size()-1].size()-1].pb(i);
}
else{
deque<int> tt;
tt.pb(i);
ss[ss.size()-1].pb(tt);
}
stt=1;
cot=0;
}
else{
cot+=1;
}
}
vector<int> ans;
int ye=0;
for(int i=0;i<ss.size();i++){
for(int j=0;j<ss[i].size();j++){
//cout<<j<<":";
while(ss[i][j].size()>4){
int aa=ss[i][j].back();
ss[i][j].pop_back();
int bb=ss[i][j].back();
ss[i][j].pop_back();
int cc=ss[i][j].back();
ss[i][j].pop_back();
ans.pb(bb);
ss[i][j].pb(bb);
}
}
//cout<<",,"<<endl;
if(ss[i].size()==1){
ye=1;
break;
}
for(int j=0;j<ss[i].size();j++){
dp[j][0]=0;
dp[j][1]=0;
dp[j][2]=0;
}
for(int j=1;j<=2;j++){
if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
dp[1][j]=1;
back[1][j]=j;
// cout<<j<<"<"<<'\n';
}
}
for(int j=2;j<ss[i].size();j++){
for(int jj=0;jj<=ss[i][j].size();jj++){
if(jj>2){
break;
}
for(int ii=0;ii<=2;ii++){
if(ii+jj==0){
continue;
}
if(((int)((int)ss[i][j-1].size()))>=ii+jj){
if(((int)(ss[i][j-1].size()))%2==(ii+jj)%2){
if(dp[j-1][ii]==1){
dp[j][jj]|=dp[j-1][ii];
back[j][jj]=ii;
// cout<<jj<<",,"<<ii<<endl;
}
}
}
}
}
}
ye=1;
// cout<<back[2][2]<<endl;
for(int ko=ss[i].back().size();ko>0;ko-=2){
if(dp[ss[i].size()-1][ko]){
ye=0;
// cout<<ko<<"//"<<endl;
vector<int> jj;
jj.pb(ko);
for(int ii=ss[i].size()-1;ii>0;ii--){
// cout<<ii<<".."<<jj.back()<<endl;
// cout<<back[ii][jj.back()]<<endl;
int xo=back[ii][jj.back()];
jj.pb(xo);
}
reverse(jj.begin(),jj.end());
/* for(auto jo:jj){
cout<<jo<<".";
}+
cout<<endl;*/
vector<int> mm;
for(int j=0;j<ss[i].size();j++){
mm.pb(ss[i][j].size());
}
for(int j=0;j<ss[i].size();j++){
int le=mm[j]-jj[j];
if(j>0){
if(j<(int)(ss[i].size())-1){
le-=jj[j+1];
}
}
/*if(le<0){
while(true){
continue;
}
}*/
/*if(le<0){
while(true){
continue;
}
}*/
// cout<<le<<"///"<<endl;
for(int jo=0;jo<le/2;jo++){
/*if(ss[i][j].size()<3){
while(true){
continue;
}
}*/
int aa=ss[i][j].back();
ss[i][j].pop_back();
int bb=ss[i][j].back();
ss[i][j].pop_back();
int cc=ss[i][j].back();
ss[i][j].pop_back();
ans.pb(bb);
ss[i][j].pb(bb);
}
// cout<<11<<endl;
}
//cout<<endl;
for(int j=0;j<(ss[i].size())-1;j++){
for(int pp=0;pp<jj[j+1];pp++){
/*if(ss[i][j].size()==0 or ss[i][j+1].size()==0){
while(true){
continue;
}
}*/
int aa=ss[i][j].back();
ss[i][j].pop_back();
int bb=ss[i][j+1].front();
ss[i][j+1].pop_front();
int x=*ac.lower_bound(aa);
ans.pb(x);
}
}
break;
}
}
if(ye){
break;
}
}
if(ye){
cout<<-1<<'\n';
continue;
}
cout<<ans.size()<<'\n';
for(auto j:ans){
cout<<j+1<<" ";
}
cout<<'\n';
}
return 0;
}
Compilation message
del13.cpp: In function 'int main()':
del13.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::deque<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0;i<ss.size();i++){
| ~^~~~~~~~~~
del13.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int j=0;j<ss[i].size();j++){
| ~^~~~~~~~~~~~~
del13.cpp:88:10: warning: unused variable 'aa' [-Wunused-variable]
88 | int aa=ss[i][j].back();
| ^~
del13.cpp:92:10: warning: unused variable 'cc' [-Wunused-variable]
92 | int cc=ss[i][j].back();
| ^~
del13.cpp:103:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j=0;j<ss[i].size();j++){
| ~^~~~~~~~~~~~~
del13.cpp:110:23: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
110 | if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
| ~~~~~~~~~~~~~~~^~~
del13.cpp:110:46: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
110 | if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
| ~~~~~~~~~~~~~~~^~~
del13.cpp:110:71: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
110 | if(ss[i][1].size()>=j and ss[i][0].size()>=j and ss[i][0].size()%2==j%2){
| ~~~~~~~~~~~~~~~~~^~~~~
del13.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for(int j=2;j<ss[i].size();j++){
| ~^~~~~~~~~~~~~
del13.cpp:117:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int jj=0;jj<=ss[i][j].size();jj++){
| ~~^~~~~~~~~~~~~~~~~
del13.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | for(int j=0;j<ss[i].size();j++){
| ~^~~~~~~~~~~~~
del13.cpp:162:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for(int j=0;j<ss[i].size();j++){
| ~^~~~~~~~~~~~~
del13.cpp:186:12: warning: unused variable 'aa' [-Wunused-variable]
186 | int aa=ss[i][j].back();
| ^~
del13.cpp:190:12: warning: unused variable 'cc' [-Wunused-variable]
190 | int cc=ss[i][j].back();
| ^~
del13.cpp:198:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int j=0;j<(ss[i].size())-1;j++){
| ~^~~~~~~~~~~~~~~~~
del13.cpp:207:12: warning: unused variable 'bb' [-Wunused-variable]
207 | int bb=ss[i][j+1].front();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
640 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
8 ms |
3832 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
2 ms |
768 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
