非常有意思的思维题。
首先我先瑞平一下翻译，我根本没看懂，还是去看英文题面看懂的。
首先可以发现整个字符串被拆成了若干个奇回文串与偶回文串。现考虑如何判是否合法。可以发现一个回文串就是要求部分位置匹配。我们对这些匹配的位置建边，如果得到的图是联通的，那么就只能填入 \(1\) 种字符，否则就可以填入多种字符。
然后考虑构造一个解。容易想到奇回文串与偶回文串区别是相当大的。对于一个长度为 \(k\) 偶回文串，我们可在它的前面错位的放一个长度为 \(k\) 的偶回文串，这样它内部是联通的，同时也与前面联通，后面还空出来一个点，可以让后面的往前接上他。
对于一个奇回文串，我们可以发现这样的构造只适用于头和尾，不过我们幸好可以证明对于大于等于 \(3\) 个奇回文串，没有构造方案。
当 \(N\) 为偶数时，总共需要 \(N-1\) 条边使得整张图联通，而序列 \(B\) 可以为我们提供 \(\frac{N}{2}\) 条边，由于上面有大于等于 \(3\) 个奇回文串，因此至多有 $ \lfloor \frac{N-3}{2} \rfloor \leq \frac{N}{2}-2$ 条边，因此整张图必定不联通。
对于 \(N\) 为奇数有类似的证明。
注意特殊处理第 \(1\) 个与最后一个，还有只有 \(1\) 个的情况。
code:
#include<iostream>
using namespace std;
const int MX=1e5+7;
int a[MX],A[MX],B[MX];
int main(){
int n,m,cnt=0;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
if(a[i]&1)cnt++;
}
if(cnt>=3){
cout<<"Impossible"<<endl;
return 0;
}
int l=1,r=n;
for(int i=1;i<=m;i++)
if(a[i]&1){
if(l==1){
l++;
A[1]=a[i];
}
else{
r--;
A[m]=a[i];
}
}
for(int i=1;i<=m;i++)
if(!(a[i]&1))A[l++]=a[i];
int tot=0;
if(m!=1){
for(int i=1;i<=m;i++){
if((A[i]&1)){
if((A[i]-1+(i==m?2:0)!=0))B[++tot]=A[i]-1+(i==m?2:0);
}
else{
if(A[i]-(i==1?1:0)!=0)B[++tot]=A[i]-(i==1?1:0);
if(i==m)B[++tot]=1;
}
}
}
else{
if(A[1]!=1)B[++tot]=A[1]-1;
B[++tot]=1;
}
for(int i=1;i<=m;i++)cout<<A[i]<<' ';
cout<<endl;
cout<<tot<<endl;
for(int i=1;i<=tot;i++)cout<<B[i]<<' ';
cout<<endl;
return 0;
}