Jumpring

문제

길이가 $N$인 문자열 $S=s_1, s_2, \cdots, s_N$가 주어진다. 승우는 이 문자열에서 0개 이상의 문자를 제거하여 길이가 $M$인 새로운 문자열 $U$를 만들고자 한다. 두 문자열은 영어 소문자로 이루어져 있으며, $M$은 $N$보다 작거나 같다.

이때 승우는 서로 인접한 두 문자를 제거할 수는 없다. 즉, 승우는 다음과 같이 문자를 제거한다.

• 제거할 문자의 개수 $K(0\le K\le \lceil \frac{N}{2}\rceil)$를 선택한다.
• 길이가 $K$인 정수열 $x_1, x_2, \cdots , x_K\ (1\le x_i \le N)$을 구성하는데, 이 정수열은 오름차 순으로 정렬되어 있고, 인접한 두 수의 차가 2 이상이다.
• $S$에서 $s_{x_1}, s_{x_2}, \cdots, s_{x_K}$를 제거한다.

$S$에서 0개 이상의 문자를 제거하여 $U$를 만들 수 있는지 판별하는 프로그램을 작성해 보자.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \leq T \leq 10\,000)$

각 테스트 케이스의 첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(1\le M \le N \le 100\,000)$

둘째 줄에 문자열 $S$가 주어진다.

셋째 줄에 문자열 $U$가 주어진다.

$S$와 $U$는 영어 소문자로 이루어져 있으며, 모든 테스트 케이스에서 $N\times M$의 합은 $2\times 10^7$을 초과하지 않는다.

출력

각 테스트 케이스에 대해서, $S$를 $T$로 만들 수 있다면 YES를, 만들 수 없다면 NO를 한 줄씩 출력한다.

예제 입력 1

2
7 4
abcdefg
aceg
7 5
abcdefg
abefg

예제 출력 1

YES
NO

• 첫 번째 테스트 케이스에서는, $S$에서 $s_2$, $s_4$, $s_6$을 제거하면 $U$를 만들 수 있다.
• 두 번째 테스트 케이스에서는, $S$를 $U$로 만들기 위해서 $s_3$과 $s_4$를 제거해야 하지만, 서로 인접한 두 문자를 제거할 수는 없으므로 $U$를 만들 수 없다.