P15088 [UOI 2025 II Stage] Digital Game

Vus the Cossack and Us the Cossack are playing a game on a string $s$ of length $n$, consisting of digits $0$-$9$. The players take turns (Vus starts) removing any digit from the string $s$. If at any moment there are two identical digits next to each other in the string, Us wins. If all digits are removed and Us has not won, then Vus wins. Vus the Cossack is so impatient that even before the game starts, he wants to know if he can win with optimal play (when both players always play to win) against Us, and he has asked you to find this out.

The first line contains $t$ $(1\leq t \leq 10)$ --- the number of subtests. In each test case: The first line contains a single integer $n$ $(1\leq n \leq 10^6)$. The second line contains a string $s$ of length $n$, consisting only of digits $0$-$9$. It is guaranteed that the sum of $n$ across all subtests does not exceed $10^6$.

For each of the $t$ lines, output $\tt{Yes}$ if Cossack Vus can win; or $\tt{No}$ otherwise.

In the first example, two identical digits will never be next to each other, as each digit appears no more than once. In the second example, Vus can take the last $2$. Then, if Us takes $1$ or $2$, Vus takes $2$ or $1$ respectively, and then all digits become different; thus, Vus will win. However, if Us takes $3$ or $5$, then Vus will take any $2$ first, and then any $1$. In the third example, Us wins even before the game starts. ### Scoring - ($8$ points): the number of different digits $\leq 2$; - ($8$ points): the number of different digits $\leq 5$; - ($6$ points): the number of different digits $\leq 7$; - ($8$ points): only one digit appears more than once; - ($7$ points): if $s_l=s_r, s_i=s_j $ and $s_i \neq s_l$ $(l\neq r; i\neq j)$, then the intervals $[l, r]$ and $[i, j]$ do not overlap; - ($7$ points): $n \leq 4$; - ($6$ points): $n \leq 8$; - ($6$ points): $n \leq 12$; - ($6$ points): $n \leq 15$; - ($38$ points): no additional restrictions.