有$$$n$$$个节点排列成圆圈,编号从$$$1$$$到$$$n$$$,按顺时针顺序。您还将获得一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。
你的任务是在给定的 $$$n$$$ 节点上构造一棵树,满足以下两个条件,或者报告这样的树不存在:
- 对于每个节点 $$$i$$$ $$$(1 \le i \le n)$$$,如果 $$$s_i = 0$$$,则节点的度为偶数;如果 $$$s_i = 1$$$,则节点的度为奇数。
- 树的任何两条边都不会在圆内部相交。允许边缘在圆周上相交。
请注意,所有边缘均绘制为直线段。例如,树中的边 $$$(u, v)$$$ 被绘制为圆上连接 $$$u$$$ 和 $$$v$$$ 的线段。
$$$n$$$ 节点上的树是具有 $$$n - 1$$$ 边的连通图。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 2\cdot 10^4)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \leq n \leq 2\cdot 10^5)$$$ — 节点数。
每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果不存在满足给定条件的树,则输出“NO”(不带引号),否则输出“YES”,后跟树的描述。
您可以在任何情况下输出每个字母(例如,“YES”、“Yes”、“yes”、“yEs”、“yEs”将被识别为肯定答案)。
如果存在树,则输出 $$$n - 1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ $$$(1 \leq u,v \leq n, u \neq v)$$$ 表示树中 $$$u$$$ 和 $$$v$$$ 之间的边。如果有多个可能的答案,则输出任何一个。
示例
输入 #1
3 4 0110 2 10 6 110110
输出 #1
YES 2 1 3 4 1 4 NO YES 2 3 1 2 5 6 6 2 3 4
注意
在第一个测试用例中,树如下所示:
在第二个测试用例中,只有一棵可能的树的边位于 $$$1$$$ 和 $$$2$$$ 之间,并且不满足度数约束。
在第三个测试用例中,