给定一个整数 $$$n$$$ 和一个长度为 $$$n$$$ 的二进制字符串$$$^{\text{*}}$$$ $$$s$$$。
对于长度为 $$$n$$$ 的排列 $$$^{\text{†}}$$$ $$$p$$$ 和整数 $$$x$$$,我们定义 $$$\text{find}(x)$$$ ,如以下伪代码所示:
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
我们称一个整数为 $$$x$$$ ($$$1\le x\le n$$$) 稳定 当且仅当 $$$\text{find}(x)$$$ 是 总是 不是未定义且 $$$p_{\text{find}(x)}=x$$$ 无论在伪代码过程中如何选择 $$$m$$$ 的值, 总是 都成立。
您必须构造一个长度为 $$$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$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例:
- 如果不存在这样的排列,则打印“NO”在唯一的输出行中。
- 否则,打印“是”在输出的第一行。然后在第二行输出 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1\le p_i\le n$$$) — 您构建的排列。
您可以在任何情况下输出令牌(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
如果有多个答案,您可以打印其中任何一个。
示例
输入复制
6311150000051010070010000110000100110012011100010000
输出复制
YES1 2 3YES2 4 3 5 1NOYES2 1 3 5 7 6 4YES2 1 4 3 5 7 6 8 9 11 10NO
注意
在第一个测试用例中,我们构造了$$$p=[1,2,3]$$$。以$$$\text{find(2)}$$$为例:
- 一开始,$$$l=1$$$ 和 $$$r=3$$$;
- 我们将选择 $$$m$$$ 作为 $$$l=1$$$ 和 $$$r=3$$$ 之间的随机整数。
- 如果我们选择 $$$m=1$$$:
- $$$p_1=1 \lt 2$$$,因此 $$$l$$$ 设置为 $$$m + 1 = 2$$$。现在$$$l=2$$$ 和$$$r=3$$$;
- 我们将选择 $$$m$$$ 作为 $$$l=2$$$ 和 $$$r=3$$$ 之间的随机整数。
- 如果我们选择$$$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=1$$$:
- 因此,无论过程中如何选择$$$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$$$;
- 我们将选择 $$$m$$$ 作为 $$$l=1$$$ 和 $$$r=5$$$ 之间的随机整数。我们选择$$$m=2$$$;
- $$$p_2=4 \gt 3$$$,因此 $$$r$$$ 设置为 $$$m-1=1$$$。现在$$$l=1$$$ 和$$$r=1$$$;
- 我们将选择 $$$m$$$ 作为 $$$l=1$$$ 和 $$$r=1$$$ 之间的随机整数。我们只能选择$$$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]$$$,也是有效的答案。您可以打印其中任何一个。
在第三个测试用例中,可以证明不存在这样的排列。