[Solution] Circular Spanning Tree Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Circular Spanning Tree Codeforces Solution | Codeforces Problem Solution 2022

D. Circular Spanning Tree

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There are 𝑛$n$ nodes arranged in a circle numbered from 1$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≤𝑖≤𝑛)$(1\le i\le n)$, the degree of node is even if 𝑠𝑖=0$s_i=0$ and odd if 𝑠𝑖=1$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.

Solution Click Below:-  CLICK HERE

Input

The input consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤2⋅104)$(1\le t\le 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≤𝑛≤2⋅105)$(2\le n\le 2\cdot {10}^5)$  — the number of nodes.

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

Palindromic Indices Codeforces Solution

AND Sorting Codeforces Solution 

LIS or Reverse LIS? Codeforces Solution

Circular Spanning Tree Codeforces Solution

Unordered Swaps Codeforces Solution

MCMF? Codeforces Solution

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

Output

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