Вам задана строка \(s\). Вы можете построить новую строку \(p\) из \(s\), используя следующую операцию не более двух раз:
Конечно, в начале строка \(p\) является пустой.
Например, пусть \(s = \text{ababcd}\). Сначала выберем подпоследовательность \(s_1 s_4 s_5 = \text{abc}\) — в результате мы получим \(s = \text{bad}\) и \(p = \text{abc}\). Потом, выберем \(s_1 s_2 = \text{ba}\) — мы получим \(s = \text{d}\) и \(p = \text{abcba}\). Таким образом, возможно построить \(\text{abcba}\) из \(\text{ababcd}\).
Можно ли построить заданную строку \(t\), используя описанный выше алгоритм?
В первой строке задано единственное число \(T\) (\(1 \le T \le 100\)) — количество наборов входных данных.
В следующих \(2T\) строках заданы сами наборы — по две строки на набор. В первой строке задана строка \(s\), состоящая из строчных букв латинского алфавита (\(1 \le |s| \le 400\)) — первоначальная строка.
Во второй строке задана строка \(t\), состоящая из строчных букв латинского алфавита (\(1 \le |t| \le |s|\)) — строка, которую вам надо построить.
Гарантируется, что суммарная длина строк \(s\) не превосходит \(400\).
Выведите \(T\) ответов — по одному на набор. Выведите YES (регистр не важен), если возможно построить \(t\), и NO (регистр не важен) иначе.
4 ababcd abcba a b defi fed xyz x
YES NO NO YES
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач