[Solution] Unordered Swaps Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Unordered Swaps Codeforces Solution | Codeforces Problem Solution 2022

E. Unordered Swaps

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Alice had a permutation 𝑝$p$ of numbers from 1$1$ to 𝑛$n$. Alice can swap a pair (𝑥,𝑦)$(x,y)$ which means swapping elements at positions 𝑥$x$ and 𝑦$y$ in 𝑝$p$ (i.e. swap 𝑝𝑥$p_x$ and 𝑝𝑦$p_y$). 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 𝑝=[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 2$2$ 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 𝑝=[2,1,4,3]$p=[2,1,4,3]$ even if it sorts the permutation because 𝑝$p$ can be sorted in 2$2$ swaps, for example using the sequence [(4,3),(1,2)]$[(4,3),(1,2)]$.

Solution Click Below:-  CLICK HERE

Input

The first line contains 2$2$ integers 𝑛$n$ and 𝑚$m$ (2≤𝑛≤2⋅105,1≤𝑚≤𝑛−1)$(2\le n\le 2\cdot {10}^5,1\le m\le n-1)$  — the size of permutation and the minimum number of swaps required to sort the permutation.

The next line contains 𝑛$n$ integers 𝑝1,𝑝2,...,𝑝𝑛$p_1,p_2,...,p_n$ (1≤𝑝𝑖≤𝑛$1\le p_i\le n$, all 𝑝𝑖$p_i$ are distinct)  — the elements of 𝑝$p$. It is guaranteed that 𝑝$p$ forms a permutation.

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

Then 𝑚$m$ lines follow. The 𝑖$i$-th of the next 𝑚$m$ lines contains two integers 𝑥𝑖$x_i$ and 𝑦𝑖$y_i$  — the 𝑖$i$-th swap (𝑥𝑖,𝑦𝑖)$(x_i,y_i)$.

It is guaranteed that it is possible to sort 𝑝$p$ with these 𝑚$m$ swaps and that there is no way to sort 𝑝$p$ with less than 𝑚$m$ swaps.

Output

Print a permutation of 𝑚$m$ integers  — a valid order of swaps written by Alice that sorts the permutation 𝑝$p$. See sample explanation for better understanding.

In case of multiple possible answers, output any.