Bessie has a computer with a keyboard that only has two letters, M and O.

Bessie wants to type her favorite moo \(S\) consisting of \(N\) letters, each of
which is either an M or an O. However, her computer has been hit with a virus.
Every time she tries to type the letter O, every letter that she has typed so
far flips, either from M to O or from O to M, before the O appears.

Is it possible for Bessie to type out her favorite moo?

Additionally, Bessie is given a parameter \(k\) which is either \(0\) or \(1\).

• If \(k = 0\), then Bessie only needs to determine whether it is possible to type out her favorite moo.
• If \(k = 1\), then Bessie also needs to give an example of a sequence of keystrokes to type so she can type out her favorite moo.

Problem credits: Nick Wu

SCORING

• Inputs 3-4: \(k=0\).
• Inputs 5-6: \(k=1, T \le 10^3, N \le 10\).
• Inputs 7-9: \(k=1, T \le 10, N \le 1000\).
• Inputs 10-16: \(k=1\).

Problem credits: Nick Wu

The first line contains \(T\), the number of independent test cases
(\(1\le T\le 10^4\)) and \(k\) (\(0 \le k \le 1\)).

The first line of each test case has \(N\) (\(1 \le N \le 2 \cdot 10^5\)).

The second line of each test case has \(S\). It is guaranteed that no characters
will appear in \(S\) besides \(\texttt{M}\) and \(\texttt{O}\).

The sum of \(N\) across all test cases will not exceed \(4 \cdot 10^5\).

For each test case, output either one or two lines using the following
procedure.

If it is impossible for Bessie to type out \(S\), print \(\texttt{NO}\)
on a single line.

Otherwise, on the first line print \(\texttt{YES}\). Furthermore, if \(k=1\), on the
second line, print a string of length \(N\), the characters in order that Bessie
needs to type in order to type out her favorite moo. If there are multiple such
strings, any will be accepted.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > Second Contest > Bronze