34538번 - Jumpring

문제

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

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

• 제거할 문자의 개수 $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$를 $U$로 만들 수 있다면 YES를, 만들 수 없다면 NO를 출력한다.

제한

힌트