Codeforces Round 685 (Div. 2) |
---|
Закончено |
У Ashish есть две строки $$$a$$$ и $$$b$$$ длины $$$n$$$ и целое число $$$k$$$. Строки содержат только строчные буквы латинского алфавита.
Он хочет превратить строку $$$a$$$ в строку $$$b$$$, исполнив несколько (возможно, ноль) операций над $$$a$$$.
За одну операцию он может сделать одно из двух возможных действий:
Обратите внимание, что он может исполнить любое число операций, и операции можно выполнять только на строке $$$a$$$.
Помогите Ashish определить, возможно ли превратить $$$a$$$ в $$$b$$$, сделав несколько (возможно, ноль) операций на ней.
В первой строке записано одно целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ ($$$2 \leq n \leq 10^6$$$) и $$$k$$$ ($$$1 \leq k \leq n$$$).
Во второй строке записана одна строка $$$a$$$ длины $$$n$$$, состоящая только из строчных букв латинского алфавита.
В третьей строке записана одна строка $$$b$$$ длины $$$n$$$, состоящая только из строчных букв латинского алфавита.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите «Yes», если Ashish может превратить $$$a$$$ в $$$b$$$ после некоторого числа операций, иначе выведите «No».
Вы можете выводить каждый символ в любом регистре (верхнем или нижнем).
4 3 3 abc bcd 4 2 abba azza 2 1 zz aa 6 2 aaabba ddddcc
No Yes No Yes
В первом наборе входных данных можно доказать, что невозможно превратить $$$a$$$ в $$$b$$$.
Во втором наборе входных данных
«abba» $$$\xrightarrow{\text{inc}}$$$ «acca» $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ «azza».
Здесь «swap» обозначает операцию первого типа, а «inc» обозначает операцию второго типа.
В третьем наборе входных данных
«aaabba» $$$\xrightarrow{\text{swap}}$$$ «aaabab» $$$\xrightarrow{\text{swap}}$$$ «aaaabb» $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ «ddaabb» $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ «ddddbb» $$$\xrightarrow{\text{inc}}$$$ $$$\ldots$$$ $$$\xrightarrow{\text{inc}}$$$ «ddddcc».
Название |
---|