## Circular Spanning Tree solution codeforces

There are nn nodes arranged in a circle numbered from 11 to nn in the clockwise order. You are also given a binary string ss of length nn.

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

- For each node ii (1≤i≤n)(1≤i≤n), the degree of node is even if si=0si=0 and odd if si=1si=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)(u,v) in the tree is drawn as a line segment connecting uu and vv on the circle.

A tree on nn nodes is a connected graph with n−1n−1 edges.

## Circular Spanning Tree solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤2⋅104)(1≤t≤2⋅104) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer nn (2≤n≤2⋅105)(2≤n≤2⋅105) — the number of nodes.

The second line of each test case contains a binary string ss of length nn.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

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−1n−1 lines, each containing two integers uu and vv (1≤u,v≤n,u≠v)(1≤u,v≤n,u≠v) denoting an edge between uu and vv in the tree. If there are multiple possible answers, output any.

## Circular Spanning Tree solution codeforces

3 4 0110 2 10 6 110110

- Contestants ranked
**1st**will win a Apple HomePod mini - Contestants ranked
**2nd**will win a Logitech G903 LIGHTSPEED Gaming Mouse - Contestants ranked
**3rd ~ 5th**will win a LeetCode Backpack - Contestants ranked
**6th ~ 10th**will win a LeetCode water bottle - Contestants ranked
**11th ~ 20th**will win a LeetCode Big O Notebook

YES 2 1 3 4 1 4 NO YES 2 3 1 2 5 6 6 2 3 4

## Circular Spanning Tree solution codeforces

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

In the third test case,