You are given a permutation $P$
of number $1, \cdots , n$
(I.E. each number occurs exactly once). Now you want to introduce some chaos to this permutation. To introduce chaos, you can perform at most $k$
swaps between adjacent positions. The chaosness of the final permutation is calculated as the count of the mismatches I.E. the number of indices $i$
such that $P[i] \neq i$
(the indices are 1-indexed). Output the maximum number of mismatch you can make and also output such a sequence of swaps.
There will be $T$
testcases.
Each testcase begins with a line containing space separated numbers $n$
, $k$
. Next line contains $n$
space separated numbers representing the initial permutation.
$1 \leq T \leq 10^5$
$3 \leq n \leq 10^5$
$0 \leq k \leq n$
sum of $n$
over all testcases $ \leq 10^5 $
For each testcase first output one number $s$
in a line, $s$
is the number of swaps you will perform. In the next $s$
lines, output the swaps to be performed. To swap positions $x$
and $y$
output the numbers $x$
and $y$
. Note that the swaps you perform should be between adjacent positions.
In case of multiple answer, you can output any.
Input | Output |
---|---|
2 4 2 1 4 2 3 10 2 1 2 3 4 5 6 7 8 9 10 | 1 1 2 2 1 2 9 10 |