20265번 - Puzzle Game 스페셜 저지다국어

For a string S, define Adjacency(S) to be the multiset of unordered pairs (S[i], S[i + 1]), i = 1, 2, ..., |S| − 1, and define Σ(S) to be the multiset of S[i], i = 1, 2, ..., |S|, where |S| is the length of S and S[i] is the ith character of S. For example, for S = ABADDADCAB, we have Adjacency(S) = {AB, BA, AD, DD, DA, AD, DC, CA, AB} = {AB, AB, AB, AC, AD, AD, AD, CD, DD} and Σ(S) = {A, A, A, A, B, B, C, D, D, D}.

John is playing a puzzle game, in which two strings P and Q, |P| > |Q|, over the character set {A, B, C, D} are given and the goal is to insert characters into Q to obtain a string Q′ such that Σ(Q′) = Σ(P) and Adjacency(Q′) = Adjacency(P). For example, given P = ABADCAB and Q = CBB, by inserting A, D, A, A into Q, we can obtain a string Q′ = ADCABAB, in which inserted characters are underlined. It is easy to check that Σ(Q′) = Σ(P) = {A, A, A, B, B, C, D} and Adjacency(Q′) = Adjacency(P) = {AB, AB, AB, AC, AD, CD}. Thus, Q′ is a solution for P = ABADCAB and Q = CBB. As another example, for P = ABA and Q = CB, there is no solution.

Please write a program to help John. More specifically, given two strings P and Q, your program computes a string Q′ such that Q′ is obtained from Q by inserting some characters, Σ(Q′) = Σ(P), and Adjacency(Q′) = Adjacency(P).

The first line of the input is an integer t, indicating that there are t test cases. Each test case consists of three lines: the first gives two integers, indicating the lengths |P| and |Q|, the second gives the string P, and the third gives the string Q.

For each case, output a solution string Q′ . If there are multiple solutions, you can output any of them. If there is no solution, output ”NO”.

• The number of test cases is at most 15.
• The length of P, |P|, is an integer between 2 and 10³.
• The length of Q, |Q|, is an integer between 1 and 10³ and |P| − 18 ≤ |Q| ≤ |P| − 1.
• Both P and Q are over the character set {A, B, C, D}.