Asterisk-Minor Template
Contest: Educational Codeforces Round 144 (Rated for Div. 2)
Difficulty rating: 1000
Tags: implementation, strings

You are given two strings $$$a$$$ and $$$b$$$, consisting of lowercase Latin letters.

A template $$$t$$$ is string, consisting of lowercase Latin letters and asterisks (character '*'). A template is called asterisk-minor if the number of asterisks in it is less than or equal to the number of letters in it.

A string $$$s$$$ is said to be matching a template $$$t$$$ if you can replace each asterisk in $$$t$$$ with a string of lowercase Latin letters (possibly, an empty string) so that it becomes equal to $$$s$$$.

Find an asterisk-minor template such that both $$$a$$$ and $$$b$$$ match it, or report that such a template doesn't exist. If there are multiple answers, print any of them.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a string $$$a$$$ ($$$1 \le |a| \le 50$$$, where $$$|a|$$$ is the length of $$$a$$$), consisting of lowercase Latin letters.

The second line contains a string $$$b$$$ ($$$1 \le |b| \le 50$$$), consisting of lowercase Latin letters.

Output format:
For each testcase, output "NO", if there doesn't exist an asterisk-minor template that both $$$a$$$ and $$$b$$$ match. Otherwise, print "YES" in the first line and the template in the second line. If there are multiple answers, print any of them.

A template should consist only of lowercase Latin letters and asterisks (character '*'). The number of asterisks should be less than or equal to the number of letters.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, for a template "*b", you can replace the only asterisk with "aaa" to get "aaab" (which is equal to $$$a$$$) or with "zzz" to get "zzzb" (which is equal to $$$b$$$).

In the third testcase, a template "*o*" is not asterisk-minor, as it contains more asterisks than letters. There are no asterisk-minor templates that both $$$a$$$ and $$$b$$$ match.

In the fourth testcase, for a template "a*a*a*a", you can replace all asterisks with empty strings to get "aaaa" (which is equal to $$$a$$$) or two of them with "a" and two of them with an empty string to get "aaaaaa" (which is equal to $$$b$$$).

In the fifth testcase, there are no asterisks in a template "abcd", so only "abcd" can match it (which is coincidentally both $$$a$$$ and $$$b$$$).

Example input:
6
aaab
zzzb
codeforces
atcoder
codeforces
tokitlx
aaaa
aaaaaa
abcd
abcd
c
f

Example output:
YES
*b
YES
*co*
NO
YES
a*a*a*a
YES
abcd
NO

Editorial:
What's the reason behind authors specifically asking for templates that have less or equal asterisks than letters? Well, without that the problem would be kind of trivial. A template "*" is matched by every string, so it would always work.
Hmm, let's try to make something similar to that template then. We basically have to find some part of that occurs in both strings that we can use letters on to get some freedom to use asterisks.
There are some easy cases. If the first letters of both strings are the same, then the template can be that letter followed by an asterisk. There's a symmetrical case for the last letter.
By studying the examples, you can also notice the final case: a common substring of both strings of length at least two surrounded by two asterisks. Moreover, since we only use two asterisks, we can find a substring of length exactly two (which always exists if a longer common substring exists).
Turns out, that's it. If a template exists, one of these three kinds also exists.
This is not that hard to show. If the first two kinds don't work, then you have to use asterisks on both sides of the template. In order for the template with asterisks on both sides to work, there have to be adjacent letters in it at least once (otherwise, it's like "*a*a*a*", and there are more asterisks than letters). And since at least one such substring exists, we can just remove everything other than this substring and the asterisks on the sides.
Overall complexity: $$$O(|a| \cdot |b|)$$$ per testcase.