1681C.md (1596B)
1 Source: https://codeforces.com/problemset/problem/1681/C 2 3 C. Double Sort 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two arrays $a$ and $b$, both consisting of $n$ integers. 22 23 In one move, you can choose two indices $i$ and $j$ ($1 \le i, j \le n$; $i \neq j$) and swap $a_i$ with $a_j$ and $b_i$ with $b_j$. You have to perform the swap in both arrays. 24 25 You are allowed to perform at most $10^4$ moves (possibly, zero). Can you make both arrays sorted in a non-decreasing order at the end? If you can, print any sequence of moves that makes both arrays sorted. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of testcases. 30 31 The first line of each testcase contains a single integer $n$ ($2 \le n \le 100$) — the number of elements in both arrays. 32 33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the first array. 34 35 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) — the second array. 36 37 Output 38 39 For each testcase, print the answer. If it's impossible to make both arrays sorted in a non-decreasing order in at most $10^4$ moves, print -1. Otherwise, first, print the number of moves $k$ $(0 \le k \le 10^4)$. Then print $i$ and $j$ for each move $(1 \le i, j \le n$; $i \neq j)$. 40 41 If there are multiple answers, then print any of them. You don't have to minimize the number of moves. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 2 51 52 1 2 53 54 1 2 55 56 2 57 58 2 1 59 60 1 2 61 62 4 63 64 2 3 1 2 65 66 2 3 2 3 67 ``` 68 69 Output 70 71 ``` 72 0 73 -1 74 3 75 3 1 76 3 2 77 4 3 78 ```