#include <bits/extc++.h>
using namespace __gnu_pbds;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fi first
#define se second
ll n,m;
string a[1000005],b[1000005];
const ll base=2977;
void add(ull &x,char c){
    x = (x * base + c);
}
pair<int,int>g[1000005],h[1000005];

gp_hash_table<ull, ll> mp,mp1,mp2;
bool check0(){
	mp.clear();
	int sz=0;
	
	for(int i=1; i<=n ;i++){
		ull hsh = 0;
		for(auto c:a[i]) add(hsh,c);
		if(mp[hsh]==0) mp[hsh]=++sz;
		g[i]={mp[hsh],i};
	}
	for(int i=1; i<=n ;i++){
		ull hsh = 0;
		for(auto c:b[i]) add(hsh,c);
		if(mp[hsh]==0) mp[hsh]=++sz;
		h[i]={mp[hsh],i};
	}
	sort(g+1,g+n+1);sort(h+1,h+n+1);
	for(int i=1; i<=n ;i++) if(g[i].fi!=h[i].fi) return false;
	for(int i=1; i<=n ;i++) cout << g[i].se << ' ';
	cout << '\n';
	for(int i=1; i<=n ;i++) cout << h[i].se << ' ';
	cout << '\n';
	return true;
}

const int N=4e6+5;
vector<pair<int,int> >adj[N];
int in[N],out[N];
vector<int>ans;
void dfs(int id){
	//if(adj[id].empty()) return;
	while(!adj[id].empty()){
		auto c=adj[id].back();adj[id].pop_back();
		dfs(c.se);
		ans.push_back(c.fi);
	}
}
void adde(int u,int v,int w){
	//cout << "Adde " << u << ' ' << v << ' ' << w << endl;
	adj[u].push_back({w,v});
	out[u]++;in[v]++;
}
bool check(int p){
	//cout << "Check " << p << endl;
	mp1.clear();mp2.clear();
	int sz=0;
	for(int i=1; i<=4*n ;i++){
		adj[i].clear();
		in[i]=0;out[i]=0;
	}
	for(int i=1; i<=n ;i++){
		ull hsh = 0;
		for(int j=0; j<p ;j++) add(hsh,a[i][j]);
		if(mp1[hsh]==0) mp1[hsh]=++sz;
		int v1=mp1[hsh];
		
		hsh = 0;
		for(int j=p; j<m ;j++) add(hsh,a[i][j]);
		if(mp2[hsh]==0) mp2[hsh]=++sz;
		int v2=mp2[hsh];
		adde(v1,v2,i);
	}
	for(int i=1; i<=n ;i++){
		ull hsh = 0;
		for(int j=m-p; j<m ;j++) add(hsh,b[i][j]);
		if(mp1[hsh]==0){
            return false;
        }
		int v1=mp1[hsh];
		
		hsh = 0;
		for(int j=0; j<m-p ;j++) add(hsh,b[i][j]);
		if(mp2[hsh]==0){
            return false;
        }
		int v2=mp2[hsh];
		adde(v2,v1,i+n);
	}
	for(int i=1; i<=sz ;i++) if(in[i]!=out[i]) return false;
	ans.clear();
	dfs(1);
	if(ans.size()!=2*n) return false;
	reverse(ans.begin(),ans.end());
	for(int i=0; i<2*n ;i+=2) cout << ans[i] << ' ';
	cout << '\n';
	for(int i=1; i<2*n ;i+=2) cout << ans[i]-n << ' ';
	cout << '\n';
	return true;
}

clock_t timer;
bool time_left(){
    return (((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC) <= 3;
}

void solve(){
    timer = clock();
	cin >> n >> m;
	for(int i=1; i<=n ;i++) cin >> a[i];
	for(int i=1; i<=n ;i++) cin >> b[i];

    vector<int> permutation(m - 1);
    for(int j = 0; j < m - 1; ++j)
        permutation[j] = j + 1;

    shuffle(permutation.begin(), permutation.end(), mt);

	if(check(0)) return;
	for(int j: permutation){
        if(!time_left()) break;
		if(check(j)) return;
	}
	cout << "-1\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;while(t--) solve();
}

answer.code: In function ‘void solve()’:
answer.code:124:53: error: ‘mt’ was not declared in this scope; did you mean ‘tm’?
  124 |     shuffle(permutation.begin(), permutation.end(), mt);
      |                                                     ^~
      |                                                     tm