2084C.md (2720B)
1 Source: https://codeforces.com/problemset/problem/2084/C 2 3 C. You Soared Afar With Grace 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 a permutation $a$ and $b$ of length $n$$^{\text{∗}}$. You can perform the following operation at most $n$ times: 22 23 * Choose two indices $i$ and $j$ ($1 \le i, j \le n$, $i \ne j$), swap $a_i$ with $a_j$, swap $b_i$ with $b_j$. 24 25 Determine whether $a$ and $b$ can be reverses of each other after operations. In other words, for each $i = 1, 2, \ldots, n$, $a_i = b_{n + 1 - i}$. 26 27 If it is possible, output any valid sequence of operations. Otherwise, output $-1$. 28 29 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the permutations. 36 37 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). 38 39 The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$). 40 41 It is guaranteed that $a$ and $b$ are permutations of length $n$. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 44 45 Output 46 47 For each test case, if it is impossible, output $-1$ in the only line. Otherwise, output a single integer $m$ ($0 \le m \le n$) — the number of operations in the first line. In the following $m$ lines, output two integers — the indices $i$ and $j$ ($1 \le i, j \le n$, $i \ne j$) in each operation in order. If there are multiple solutions, print any of them. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 2 57 58 1 2 59 60 1 2 61 62 2 63 64 1 2 65 66 2 1 67 68 4 69 70 1 3 2 4 71 72 2 4 1 3 73 74 5 75 76 2 5 1 3 4 77 78 3 5 4 2 1 79 80 5 81 82 3 1 2 4 5 83 84 1 2 3 4 5 85 ``` 86 87 Output 88 89 ``` 90 -1 91 0 92 1 93 1 2 94 2 95 1 2 96 1 3 97 -1 98 ``` 99 100 Note 101 102 In the second test case, $b$ is already the reverse of $a$. 103 104 In the third test case, after performing the following operation, $b$ will become the reverse of $a$: 105 106 * Swap $a_1, a_2$ and swap $b_1, b_2$. Now $a = [3, 1, 2, 4]$ and $b = [4, 2, 1, 3]$. 107 108 In the fourth test case, after performing the following operations in order, $b$ will become the reverse of $a$: 109 110 * Swap $a_1, a_2$ and swap $b_1, b_2$. Now $a = [5, 2, 1, 3, 4]$ and $b = [5, 3, 4, 2, 1]$. 111 * Swap $a_1, a_3$ and swap $b_1, b_3$. Now $a = [1, 2, 5, 3, 4]$ and $b = [4, 3, 5, 2, 1]$.