#P0828. 密钥重组

密钥重组

题目描述

霓虹在远方破碎成条,雷鸣像被压低的鼓点。你蜷缩在被遗弃的前哨站地下室里,只剩一盏应急灯和一台老旧便携终端。你点亮最后一枚战术灯——屏幕上跳动的是一串看似无意义的代码。但你知道,这并非普通的杂讯,而是敌军用来掩护关键指令的“活体谜题”。情报中心发来最后一条语音:这串数据里藏着一枚关键暗号,握住它就能截断敌军的命令链,扭转前线局势,成败......在此一举......

在一次秘密任务中,你截获了一段敌方的加密数据串 ss。

情报部门确认,这段数据中隐藏着一段关键暗号tt,只要找到它,就能解开敌军的通信协议。

不过,这段加密数据被设计成不断扰乱顺序。你只能通过两种“破解手段”来操作这段数据:

  • 操作11 - 镜像反转:你可以将整段数据镜像翻转。即将s[0],s[1],...,s[n−1]s[0], s[1], ... ,s[n - 1]变成s[n−1],s[n−2],...,s[0]s[n - 1], s[n - 2], ..., s[0]。
  • 操作22 - 轮转切换: 你可以选择一个位置pos(0≤pos<n−1)pos(0 \le pos < n - 1),将pospos前(包括pospos)的子串和pospos后的子串互换位置。即将s[0],s[1],...s[pos],s[pos+1],...s[n−1]s[0], s[1],... s[pos], s[pos + 1], ... s[n - 1] 变成 $s[pos + 1], s[pos + 2], ..., s[n - 1], s[0], s[1], ..., s[pos]$。

你的任务是:通过最少的操作次数,让目标暗号 tt 出现在数据串 ss 中。

成功破解后,你将获得敌军的秘密指令!

输入格式

本题包含多组测试数据。

第一行为一个整数T(1≤T≤105)T(1 \le T \le 10^5),测试数据组数。

对于每组测试数据,第一行为两个整数n,m(1≤n,m≤2×105)n, m(1 \le n,m\le 2 \times 10^5),为两个字符串的长度。

第三行为一个字符串:加密数据串ss。

第四行为一个字符串:你要找的关键暗号串tt。

数据保证:∑n≤2×105,∑m≤2×105\sum n \le 2 \times 10^5, \sum m \le 2\times 10^5,s,s和tt中仅包含小写字母。

输出格式

对于每组测试数据,输出一行一个整数,如果能找到,输出操作的最小次数;如果找不到,输出−1-1。

样例

3
6 2
aaabbb
ab
6 2
aaabbb
ba
6 2
aaabbb
bc
0
1
-1

提示

对于第一组测试数据, ss中已经包含tt,无需操作。

对于第二组测试数据,只需执行一次操作1或在pos∈{0,1,2}pos \in \{0, 1,2\}中任选一个位置执行一次操作2,即可。

对于第三组测试数据,无论执行多少次操作,也不能让ss中出现子串tt。