CF1682D.Circular Spanning Tree

There are $n$ nodes arranged in a circle numbered from $1$ to $n$ in the clockwise order. You are also given a binary string $s$ of length $n$.

Your task is to construct a tree on the given $n$ nodes satisfying the two conditions below or report that such tree does not exist:

• For each node $i$ $(1 \le i \le n)$, the degree of node is even if $s_i = 0$ and odd if $s_i = 1$.
• No two edges of the tree intersect internally in the circle. The edges are allowed to intersect on the circumference.

Note that all edges are drawn as straight line segments. For example, edge $(u, v)$ in the tree is drawn as a line segment connecting $u$ and $v$ on the circle.

A tree on $n$ nodes is a connected graph with $n - 1$ edges.

有 $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$ 条边的连通图。

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 2\cdot 10^4)$ — the number of test cases. Description of the test cases follows.

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

The second line of each test case contains a binary string $s$ of length $n$.

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

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, if there does not exist a tree that satisfies the given conditions, then output "NO" (without quotes), otherwise output "YES" followed by the description of a suitable tree.

You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

If there exists a tree, then output $n - 1$ lines, each containing two integers $u$ and $v$ $(1 \leq u,v \leq n, u \neq v)$ denoting an edge between $u$ and $v$ in the tree. If there are multiple possible answers, output any.

对于每个测试用例，若不存在满足给定条件的树，则输出 "NO"（不带引号）；否则输出 "YES"，后跟一棵符合条件的树的描述。

你可以以任意大小写形式输出每个字母（例如 "YES"、"Yes"、"yes"、"yEs"、"yEs" 均被视为肯定回答）。

如果存在这样的树，则输出 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u,v \leq n$，且 $u \neq v$），表示树中连接顶点 $u$ 和 $v$ 的一条边。若存在多种可能的答案，输出任意一种即可。

In the first test case, the tree looks as follows:

In the second test case, there is only one possible tree with an edge between $1$ and $2$, and it does not satisfy the degree constraints.

In the third test case,

The tree on the left satisfies the degree constraints but the edges intersect internally, therefore it is not a valid tree, while the tree on the right is valid.

在第一个测试用例中，树的结构如下所示：

在第二个测试用例中，仅存在一种可能的树，即节点 $1$ 与节点 $2$ 之间有一条边；但该树不满足度数约束。

在第三个测试用例中，

左侧的树满足度数约束，但其边在内部相交，因此不是一棵合法的树；而右侧的树是合法的。