Circular Spanning Tree
Contest: Codeforces Round 793 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, implementation, trees

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 there 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.

Input format:
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$$$.

Output format:
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 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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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,

Example input:
3
4
0110
2
10
6
110110

Example output:
YES
2 1
3 4
1 4
NO
YES
2 3
1 2
5 6
6 2
3 4

Editorial:
Let's check some cases when it is not possible to construct an answer
• When all vertices have an even degree. Every tree contains at least $$$2$$$ leaves.
• When there is the odd number of vertices with an odd degree. The Sum of degrees should be even.
Now we can show that it is always possible to construct the answer. Select some vertex $$$i$$$ such that the previous vertex of $$$i$$$ has an odd degree i.e. $$$s_{i - 1} = 1$$$ for $$$ i \gt 1 $$$. String is circular hence for $$$i = 1$$$, previous vertex of $$$1$$$ will be $$$n$$$.
Now left rotate $$$s$$$, $$$i - 1$$$ times such that selected vertex is now at index $$$1$$$. Note that after rotation $$$s_n$$$ will become $$$1$$$. Now we can see that $$$s[2\ldots n]$$$ can be divided into several segments such that each segment ends with some vertex having an odd degree. And each segment should contain exactly one vertex with an odd degree. So $$$s[2 \ldots n] = 0\ldots 1, 0\ldots 1, \ldots, 0\ldots 1$$$. Connect vertex $$$1$$$ to the starting vertex of each segment and connect adjacent vertices inside each segment. We can see that it will be a valid tree.
Proof:
• Degree condition is valid for each segment, as each vertex with an even degree is connected with $$$2$$$ other vertices and the vertex with an odd degree will be connected to only one vertex.
• Let $$$cnt_1$$$ be the number of vertices with odd degrees.If $$$s_1 = 1$$$, then there will $$$cnt_1 - 1$$$ segments which is an odd number, hence vertex $$$1$$$ will be connected to odd number of vertices. If $$$s_1 = 0$$$, then there will be $$$cnt_1$$$ segments which is an even number, hence vertex $$$1$$$ will be connected to even number of vertices.
Overall, The solution can be implemented in $$$\mathcal{O(n)}$$$.