GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Sunday 22 May 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 to n. Alice can swap a pair (x,y) which means swapping elements at positions x and y in p (i.e. swap px and py). 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)] is a valid swap sequence by Alice for permutation p=[3,1,2] whereas [(1,3),(2,3)] is not because it doesn't sort the permutation. Note that we cannot sort the permutation in less than 2 swaps.
  • [(1,2),(2,3),(2,4),(2,3)] cannot be a sequence of swaps by Alice for p=[2,1,4,3] even if it sorts the permutation because p can be sorted in 2 swaps, for example using the sequence [(4,3),(1,2)].

Solution Click Below:-  CLICK HERE

Input

The first line contains 2 integers n and m (2n2105,1mn1)  — the size of permutation and the minimum number of swaps required to sort the permutation.

The next line contains n integers p1,p2,...,pn (1pin, all pi are distinct)  — the elements of p. It is guaranteed that p forms a permutation.

Then m lines follow. The i-th of the next m lines contains two integers xi and yi  — the i-th swap (xi,yi).

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.


No comments:

Post a Comment