35102번 - Dog Tricks 스페셜 저지다국어

문제

The videos showcasing a wide variety of tricks performed by your two pet dogs, Amy and Bessie, have become popular content in the Icpca Kingdom. To explore the potential for further videos, you taught the dogs a new trick.

The new trick is performed using plates aligned from left to right. Each plate holds either an apple or a banana.

When you command Amy, she holds a banana in her mouth and looks at each plate in turn from left to right. She skips any plate with a banana and, upon reaching the first plate with an apple, places the banana she was carrying on that plate, picks up the apple, and continues to the right. Then she skips any plate with an apple and, upon reaching the first plate with a banana, places the apple she was carrying on that plate, picks up the banana, and comes back to you, successfully completing the trick. If the fruits on the plates are not arranged in a way that allows this, the trick fails.

When you command Bessie, she holds an apple in her mouth and looks at each plate in turn from left to right. She skips any plate with an apple and, upon reaching the first plate with a banana, places the apple she was carrying on that plate, picks up the banana, and continues to the right. Then she skips any plate with a banana and, upon reaching the first plate with an apple, places the banana she was carrying on that plate, picks up the apple, and comes back to you, successfully completing the trick. If the fruits on the plates are not arranged in a way that allows this, the trick fails.

You cannot command both dogs simultaneously, nor can you command one dog while the other is performing a trick.

In the next video project, you want to rearrange the fruits on the plates into the target state by repeatedly having the dogs perform successful tricks. You are given the initial and target states of the fruits on the plates. Starting from the initial state, can you rearrange the fruits on the plates into the target state by issuing no more than a specified number of commands to Amy and Bessie in an appropriate order? If possible, find a sequence of such commands.

입력

The input consists of at most 100ドル$ test cases, each in the following format.

$n$

$s$

$t$

Each test case consists of three lines. The first line contains an integer $n$ between 1ドル$ and 100ドル,ドル inclusive, representing the number of plates. The second line contains a string $s$ representing the initial state. If the $i$-th character of $s$ is a, an apple is on the $i$-th plate from the left in the initial state; if it is b, a banana is on it. The third line contains a string $t$ representing the target state. If the $i$-th character of $t$ is a, an apple should be on the $i$-th plate from the left in the target state; if it is b, a banana should be on it. Both $s$ and $t$ consist only of a and b, and they both have length $n$. Strings $s$ and $t$ are not identical.

The end of the input is indicated by a line consisting only of a zero.

출력

For each test case, output yes in a line if there exists a sequence of 10ドル,円 000$ or less commands to the dogs that rearranges the initial state to the target state; otherwise, output no in a line. In addition, if such a sequence exists, output a string representing the command sequence in the next line. The string should consist of the characters A and B. Its $i$-th character being A means the $i$-th command is to Amy, while its being B means the command is to Bessie. If there are two or more such sequences, any of them is accepted.

제한

노트