CF2146C.Wrong Binary Search

You are given an integer $n$ and a binary string$^{\text{∗}}$ $s$ of length $n$.

For a permutation$^{\text{†}}$ $p$ of length $n$ and an integer $x$, we define $\text{find}(x)$ as in the following pseudocode:

function find(int x):    l := 1    r := n    while l <= r:        let m be a random integer between l and r (inclusive)        if p[m] == x            return m        if p[m] > x:            r := m - 1        else:            l := m + 1    return undefined     // not found

We call an integer $x$ ($1\le x\le n$) stable if and only if $\text{find}(x)$ is always not undefined and $p_{\text{find}(x)}=x$ always holds, no matter how the value of $m$ is selected in the process of the pseudocode.

You have to construct a permutation $p$ of length $n$, such that:

• For each $1\le i\le n$, the integer $i$ is stable if and only if $s_i=\mathtt{1}$.

Or determine that no such permutation exists.

$^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$.

$^{\text{†}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

给你一个整数 $n$ 和一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$。

对于一个长度为 $n$ 的排列$^{\text{†}}$ $p$ 和一个整数 $x$，我们按如下伪代码定义 $\text{find}(x)$：

function find(int x):    l := 1    r := n    while l <= r:        设 $m$ 为区间 $[l, r]$ 内任意一个随机整数（含端点）        if p[m] == x            return m        if p[m] > x:            r := m - 1        else:            l := m + 1    return undefined     // 未找到

我们称一个整数 $x$（其中 $1 \le x \le n$）是稳定的，当且仅当无论在伪代码执行过程中 $m$ 如何选取，$\text{find}(x)$ 总不返回 undefined，且总有 $p_{\text{find}(x)} = x$ 成立。

你需要构造一个长度为 $n$ 的排列 $p$，使得：

• 对每个 $1 \le i \le n$，整数 $i$ 是稳定的 当且仅当 $s_i = \mathtt{1}$。

或者判断不存在满足条件的排列。

$^{\text{∗}}$二进制字符串是指每个字符均为 $\mathtt{0}$ 或 $\mathtt{1}$ 的字符串。

$^{\text{†}}$长度为 $n$ 的排列是指由 $1$ 到 $n$ 中 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n \le 2\cdot 10^5$) — the length of the permutation.

The second line contains the binary string $s$ of length $n$ ($s_i=\mathtt{0}$ or $\mathtt{1}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n \le 2\cdot 10^5$）—— 表示排列的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $s$（其中 $s_i=\mathtt{0}$ 或 $\mathtt{1}$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

For each test case:

• If no such permutation exists, print "NO" in the only line of output.
• Otherwise, print "YES" in the first line of output. Then output $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1\le p_i\le n$) in the second line — the permutation you constructed.

You can output the token in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple answers, you may print any of them.

对于每个测试用例：

• 如果不存在这样的排列，则在输出的唯一一行中打印 “NO”。
• 否则，在输出的第一行中打印 “YES”。然后在第二行输出 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（满足 $1\le p_i\le n$）——即你构造出的排列。

你可以以任意大小写形式输出这些字符串（大写或小写均可）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答。

如果存在多个合法答案，你可以输出其中任意一个。

In the first test case, we have constructed $p=[1,2,3]$. Take $\text{find(2)}$ as an example:

• In the beginning, $l=1$ and $r=3$;
• We will select $m$ as a random integer between $l=1$ and $r=3$.
  • If we choose $m=1$:
    • $p_1=1 \lt 2$, so $l$ is set to $m + 1 = 2$. Now $l=2$ and $r=3$;
    • We will select $m$ as a random integer between $l=2$ and $r=3$.
    • If we choose $m=2$: $p_2=2$, so the return value is $2$.
    • If we choose $m=3$: $p_3=3 \gt 2$, so $r$ is set to $m-1=2$. Now $l=2$ and $r=2$, so we can only select $m=2$. $p_2=2$, so the return value is $2$.
  • If we choose $m=2$:
    • $p_2=2$, so the return value is $2$.
  • If we choose $m=3$, the process is similar to that when $m=1$ is chosen. The return value is always $2$.
• Thus, no matter how $m$ is selected during the process, the return value of $\text{find}(2)$ is always $2$.

So $p_{\text{find}(2)}= p_2 = 2$ always holds, and the integer $2$ is stable.

Similarly, we can show that integers $1$ and $3$ are also stable. Thus, the permutation $p = [1, 2, 3]$ is a valid answer.

In the second test case, we have constructed $p=[2,4,3,5,1]$. Take $\text{find(3)}$ as an example:

• In the beginning, $l=1$ and $r=5$;
• We will select $m$ as a random integer between $l=1$ and $r=5$. Let's choose $m=2$;
• $p_2=4 \gt 3$, so $r$ is set to $m-1=1$. Now $l=1$ and $r=1$;
• We will select $m$ as a random integer between $l=1$ and $r=1$. We can only choose $m=1$;
• $p_1=2 \lt 3$, so $l$ is set to $m + 1 = 2$. Now $l=2$ and $r=1$;
• Since $l \gt r$, the loop is exited and the return value is undefined.

Thus, the return value of $\text{find}(3)$ is undefined, so the integer $3$ is not stable.

Similarly, we can show that integers $1$, $2$, $4$, and $5$ are also not stable. Thus, $p = [2, 4, 3, 5, 1]$ is a valid answer.

Some other permutations, such as $p=[5,4,3,2,1]$ and $p=[3,5,1,4,2]$, are also valid answers. You may print any of them.

In the third test case, it can be proven that no such permutation exists.

在第一个测试用例中，我们构造了 $p=[1,2,3]$。以 $\text{find(2)}$ 为例：

• 初始时，$l=1$ 且 $r=3$；
• 我们将从 $l=1$ 到 $r=3$ 之间随机选取一个整数作为 $m$。
  • 若选取 $m=1$：
    • $p_1=1 \lt 2$，因此将 $l$ 更新为 $m + 1 = 2$；此时 $l=2$，$r=3$；
    • 我们将从 $l=2$ 到 $r=3$ 之间随机选取一个整数作为 $m$。
    • 若选取 $m=2$：$p_2=2$，因此返回值为 $2$。
    • 若选取 $m=3$：$p_3=3 \gt 2$，因此将 $r$ 更新为 $m-1=2$；此时 $l=2$，$r=2$，故只能选取 $m=2$；而 $p_2=2$，因此返回值为 $2$。
  • 若选取 $m=2$：
    • $p_2=2$，因此返回值为 $2$。
  • 若选取 $m=3$，其过程与选取 $m=1$ 时类似。返回值恒为 $2$。
• 因此，无论过程中 $m$ 如何选取，$\text{find}(2)$ 的返回值始终为 $2$。

于是，$p_{\text{find}(2)}= p_2 = 2$ 恒成立，整数 $2$ 是稳定的。

同理，可证整数 $1$ 和 $3$ 也均为稳定的。因此，排列 $p = [1, 2, 3]$ 是一个合法答案。

在第二个测试用例中，我们构造了 $p=[2,4,3,5,1]$。以 $\text{find(3)}$ 为例：

• 初始时，$l=1$ 且 $r=5$；
• 我们将从 $l=1$ 到 $r=5$ 之间随机选取一个整数作为 $m$；不妨取 $m=2$；
• $p_2=4 \gt 3$，因此将 $r$ 更新为 $m-1=1$；此时 $l=1$，$r=1$；
• 我们将从 $l=1$ 到 $r=1$ 之间随机选取一个整数作为 $m$；此时只能选取 $m=1$；
• $p_1=2 \lt 3$，因此将 $l$ 更新为 $m + 1 = 2$；此时 $l=2$，$r=1$；
• 由于 $l \gt r$，循环退出，返回值未定义。

因此，$\text{find}(3)$ 的返回值未定义，整数 $3$ 不稳定。

同理，可证整数 $1$、$2$、$4$ 和 $5$ 均不稳定。因此，排列 $p = [2, 4, 3, 5, 1]$ 是一个合法答案。

其他一些排列，例如 $p=[5,4,3,2,1]$ 和 $p=[3,5,1,4,2]$，同样为合法答案。你可输出其中任意一个。

在第三个测试用例中，可以证明：不存在满足条件的排列。