#P18432. The Phantom Menace
The Phantom Menace
The Phantom Menace
Putata 带来了一道字符串题。给定两个字符串序列 ,每个序列都恰有 个字符串,每个字符串的长度都是 。你需要分别重新排列这两个序列,使它们各自拼接所得的两个字符串循环同构。
具体来说,需要找出 的两个排列 ,使
与
循环同构。这里 表示字符串拼接:若 ,则前 个字符与 相同,其后的 个字符与 相同。
两个字符串 循环同构,指它们长度相同,设为 ,且存在一个循环位移 ,使对所有 ,都有
也就是说,其中一个字符串可以通过一次循环旋转变成另一个。
请找出符合条件的两个排列,或者判断不存在。
输入格式
第一行包含测试用例数 ,。
每个测试用例的第一行包含两个整数 ,满足
接下来 行,每行一个字符串,第 行是 ,长度为 。
再接下来 行,每行一个字符串,第 行是 ,长度为 。
所有字符串仅包含小写英文字母。保证所有测试用例的 之和不超过 。
输出格式
对每个测试用例,若存在符合要求的排列,在两行中分别输出 ,同行的整数以空格分隔。若有多种方案,输出任意一种。
若不存在方案,输出一行 。
完整原样例
输入:
2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def
输出:
1 3 2
1 2 3
-1