思路：
我们会发现不合法的位置只有两种情况
要么在前半边，要么在后半边
那么，我们将序列劈两次
使两次的长度分别为：
(n为偶数时要特判一下，因为根本不可能)
（n/2）,(n/2+1)
（n/2+1）,(n/2)
分别暴力贪心的匹配就好
但是，想ACACACACA这种，就会出锅
特判一下就好
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
#define p1 19260817
#define p2 998244353
using namespace std;
int n,t;
char ls[];
int hash1()
{
long long ans=;
for(rii=;i<=n/;i++)
{
ans*=ls[i];
ans%=p1;
}
return ans;
}
int hash2()
{
long long ans=;
for(rii=;i<=n/;i++)
{
ans*=ls[i];
ans%=p2;
}
return ans;
}
int pash1()
{
long long ans=;
for(rii=(n+)/+;i<=n;i++)
{
ans*=ls[i];
ans%=p1;
}
return ans;
}
int pash2()
{
long long ans=;
for(rii=(n+)/+;i<=n;i++)
{
ans*=ls[i];
ans%=p2;
}
return ans;
}
void solve()
{
scanf("%d\n",&n);
int cnt=,wz=;
for(rii=;i<=n;i++)
{
cnt++;
ls[i]=getchar();
}
scanf("\n");
if(n%==)
{
puts("NOT POSSIBLE");
return;
}
int dp=;
for(rii=;i<=n-;i++)
{
if(ls[i]!=ls[i+])
{
dp=;
break;
}
}
if(dp==)
{
puts("NOT UNIQUE");
return;
}
int bnt=n/;
int sl=,pd=;
for(int i=;i<=n/;i++)
{
bnt++;
if(ls[i]!=ls[bnt])
{
bnt++;
pd++;
if(ls[bnt]!=ls[i])
{
pd++;
}
}
if(pd>=)
{
break;
}
}
int cs1=,cs2=;
if(pd<=)
{
sl++;
cs1=hash1();
cs2=hash2();
wz=;
}
pd=,bnt=;
int kkk=(n+)/;
for(int i=kkk+;i<=n;i++)
{
bnt++;
if(ls[bnt]!=ls[i])
{
bnt++;
pd++;
if(ls[bnt]!=ls[i])
{
pd++;
}
}
if(pd>=)
{
break;
}
}
if(pd<=)
{
sl++;
wz=;
}
if(sl==)
{
if(cs1==pash1()&&cs2==pash2())
{
sl--;
}
}
if(sl==)
{
puts("NOT UNIQUE");
}
if(sl==)
{
puts("NOT POSSIBLE");
}
if(sl==)
{
if(wz==)
{
int ltt=n/;
for(rii=;i<=ltt;i++)
{
putchar(ls[i]);
}
putchar();
}
else
{
int ltt=(n+)/;
for(rii=ltt+;i<=n;i++)
{
putchar(ls[i]);
}
putchar();
}
}
}
int main()
{
freopen("lgg.in","r",stdin);
freopen("lgg.out","w",stdout);
scanf("%d\n",&t);
for(rii=;i<=t;i++)
{
solve();
}
return ;
}