好劲的字符串题，然而实际上和字符串没啥关系
比赛的时候全队应该就只有我没读过题面，感觉如果让我看到这个重排+循环同构第一反应肯定是枚举偏移量+Hash比较前后缀，因为我字符串算法高级的不会只会一个Hash，说不定能搞出点想法
但今天补的时候发现写起来细节还是挺多的，尤其是有向图的欧拉回路和无向图版本不太一样，去网上重新找了个写法才过
回到题目，循环同构的解决思路一般就是枚举一个偏移量\(x\)，之后我们发现问题转化为：
- 第一个集合中的串长度为\(x\)的前缀和第二个串中长度为\(x\)的后缀匹配
- 第二个集合中长度为\(n-x\)的前缀和第一个集合中长度为\(n-x\)的后缀匹配
一个很直观的想法就是把每个字符串看成点，然后把分割后有相同部分的关系看成边，但这样有个问题就是可能会出现边数爆炸的情况
因此不妨换个角度思考，把对应长度的前后缀看成点，然后将字符串看作边，这样图中的边数就是\(O(n)\)级别的，同时相同部分由于会映射到同一个点上，也就变相实现了匹配的功能
再手玩一下就会发现此时题目转化为在得到的图上找一个欧拉回路，然后直接上板子即可
总复杂度\(O(n\times m)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
int t,n,m,deg[N],idx; char s[N]; vector <pi> v[N];
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
int x,y;
inline Hasher(CI X=0,CI Y=0)
{
x=X; y=Y;
}
inline LL get_val(void)
{
return ((1LL*x)<<31LL)|(1LL*y);
}
friend inline bool operator == (const Hasher& A,const Hasher& B)
{
return A.x==B.x&&A.y==B.y;
}
friend inline Hasher operator + (const Hasher& A,const Hasher& B)
{
return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
}
friend inline Hasher operator - (const Hasher& A,const Hasher& B)
{
return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
}
friend inline Hasher operator * (const Hasher& A,const Hasher& B)
{
return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
}
}pw[N]; vector <Hasher> h[N]; vector <int> path; int used[N];
const Hasher seed=Hasher(31,131);
inline void init(CI n)
{
pw[0]=Hasher(1,1); for (RI i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
}
inline Hasher get_hsh(CI id,CI l,CI r)
{
return h[id][r]-h[id][l-1]*pw[r-l+1];
}
inline void DFS(CI now)
{
while (!v[now].empty())
{
int to=v[now].back().fi,id=v[now].back().se; v[now].pop_back();
if (used[id]) continue; DFS(to); used[id]=1; path.push_back(id);
}
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t),init(1e6);t;--t)
{
RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=2*n;++i)
{
h[i].resize(m+1); h[i][0]=Hasher(); scanf("%s",s+1);
for (j=1;j<=m;++j) h[i][j]=h[i][j-1]*seed+Hasher(s[j],s[j]);
}
bool sign=0; for (i=0;i<m;++i) //shift
{
for (j=1;j<=idx;++j) deg[j]=0,v[j].clear(); idx=0;
map <LL,int> rst[2]; int st;
auto get_id=[&](CI tp,const LL& val)
{
if (!rst[tp].count(val)) rst[tp][val]=++idx; return rst[tp][val];
};
for (j=1;j<=n;++j)
{
int x=get_id(0,get_hsh(j,1,i).get_val()),y=get_id(1,get_hsh(j,i+1,m).get_val());
st=x; v[x].push_back(pi(y,j)); ++deg[x]; --deg[y];
}
for (j=n+1;j<=2*n;++j)
{
int x=get_id(1,get_hsh(j,1,m-i).get_val()),y=get_id(0,get_hsh(j,m-i+1,m).get_val());
v[x].push_back(pi(y,j)); ++deg[x]; --deg[y];
}
bool flag=1; for (j=1;j<=idx;++j) if (deg[j]) { flag=0; break; }
if (!flag) continue; path.clear(); for (j=1;j<=2*n;++j) used[j]=0;
/*for (j=1;j<=idx;++j)
{
printf("%d -> ",j);
for (auto [x,y]:v[j]) printf("(%d,%d) ",x,y); putchar('\n');
}*/
DFS(st); for (j=1;j<=2*n;++j) if (!used[j]) { flag=0; break; }
if (!flag) continue; reverse(path.begin(),path.end());
vector <int> pa,pb; for (auto x:path)
if (x<=n) pa.push_back(x); else pb.push_back(x-n);
sign=1; for (auto x:pa) printf("%d ",x); putchar('\n');
for (auto x:pb) printf("%d ",x); putchar('\n'); break;
}
if (!sign) puts("-1");
}
return 0;
}