Sunday, 22 May 2022

Unordered Swaps solution codeforces- Alice had a permutation pp of numbers from 11 to nn. Alice can swap a pair (x,y)(x,y) which means swapping elements at positions xx and yy in pp (i.e. swap pxpx and pypy). Alice recently learned her first sorting algorithm, so she decided to sort her permutation in the minimum number of swaps possible. She wrote down all the swaps in the order in which she performed them to sort the permutation on a piece of paper.

  

Unordered Swaps solution codeforces

Alice had a permutation pp of numbers from 11 to nn. Alice can swap a pair (x,y)(x,y) which means swapping elements at positions xx and yy in pp (i.e. swap pxpx and pypy). Alice recently learned her first sorting algorithm, so she decided to sort her permutation in the minimum number of swaps possible. She wrote down all the swaps in the order in which she performed them to sort the permutation on a piece of paper.

For example,

  • [(2,3),(1,3)][(2,3),(1,3)] is a valid swap sequence by Alice for permutation p=[3,1,2]p=[3,1,2] whereas [(1,3),(2,3)][(1,3),(2,3)] is not because it doesn’t sort the permutation. Note that we cannot sort the permutation in less than 22 swaps.
  • [(1,2),(2,3),(2,4),(2,3)][(1,2),(2,3),(2,4),(2,3)] cannot be a sequence of swaps by Alice for p=[2,1,4,3]p=[2,1,4,3] even if it sorts the permutation because pp can be sorted in 22 swaps, for example using the sequence [(4,3),(1,2)][(4,3),(1,2)].

Unfortunately, Bob shuffled the sequence of swaps written by Alice.

You are given Alice’s permutation pp and the swaps performed by Alice in arbitrary order. Can you restore the correct sequence of swaps that sorts the permutation pp? Since Alice wrote correct swaps before Bob shuffled them up, it is guaranteed that there exists some order of swaps that sorts the permutation.

Input

Unordered Swaps solution codeforces

The first line contains 22 integers nn and mm (2n2105,1mn1)(2≤n≤2⋅105,1≤m≤n−1)  — the size of permutation and the minimum number of swaps required to sort the permutation.

The next line contains nn integers p1,p2,...,pnp1,p2,…,pn (1pin1≤pi≤n, all pipi are distinct)  — the elements of pp. It is guaranteed that pp forms a permutation.

Then mm lines follow. The ii-th of the next mm lines contains two integers xixi and yiyi  — the ii-th swap (xi,yi)(xi,yi).

It is guaranteed that it is possible to sort pp with these mm swaps and that there is no way to sort pp with less than mm swaps.

Output

Print a permutation of mm integers  — a valid order of swaps written by Alice that sorts the permutation pp. See sample explanation for better understanding.

In case of multiple possible answers, output any.

Examples

input

Copy

Unordered Swaps solution codeforces

4 3
2 3 4 1
1 4
2 1
1 3
output
  • 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

Copy

2 3 1 

input

Copy
6 4
6 5 1 3 2 4
3 1
2 5
6 3
6 4

output

Copy
4 1 3 2 
Note

In the first example, p=[2,3,4,1]p=[2,3,4,1]m=3m=3 and given swaps are [(1,4),(2,1),(1,3)][(1,4),(2,1),(1,3)].

There is only one correct order of swaps i.e [2,3,1][2,3,1].

  1. First we perform the swap 22 from the input i.e (2,1)(2,1)pp becomes [3,2,4,1][3,2,4,1].
  2. Then we perform the swap 33 from the input i.e (1,3)(1,3)pp becomes [4,2,3,1][4,2,3,1].
  3. Finally we perform the swap 11 from the input i.e (1,4)(1,4) and pp becomes [1,2,3,4][1,2,3,4] which is sorted.

In the second example, p=[6,5,1,3,2,4]p=[6,5,1,3,2,4]m=4m=4 and the given swaps are [(3,1),(2,5),(6,3),(6,4)][(3,1),(2,5),(6,3),(6,4)].

One possible correct order of swaps is [4,2,1,3][4,2,1,3].

  1. Perform the swap 44 from the input i.e (6,4)(6,4)pp becomes [6,5,1,4,2,3][6,5,1,4,2,3].
  2. Perform the swap 22 from the input i.e (2,5)(2,5)pp becomes [6,2,1,4,5,3][6,2,1,4,5,3].
  3. Perform the swap 11 from the input i.e (3,1)(3,1)pp becomes [1,2,6,4,5,3][1,2,6,4,5,3].
  4. Perform the swap 33 from the input i.e (6,3)(6,3) and pp becomes [1,2,3,4,5,6][1,2,3,4,5,6] which is sorted.

There can be other possible answers such as [1,2,4,3][1,2,4,3].

SOLUTION

Click here

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.

  

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 (1in)(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 n1n−1 edges.

Input

Circular Spanning Tree solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t2104)(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 (2n2105)(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 21052⋅105.

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

Example

input

Copy

Circular Spanning Tree solution codeforces

3
4
0110
2
10
6
110110

output

Copy
  • 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

Note

Circular Spanning Tree solution codeforces

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 11 and 22, 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.

SOLUTION

Click here