CF1882E2.Two Permutations (Hard Version)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

This is the hard version of the problem. The difference between the two versions is that you have to minimize the number of operations in this version. You can make hacks only if both versions of the problem are solved.

You have two permutations ^{\dagger} p1,p2,,pnp_{1}, p_{2}, \ldots, p_{n} (of integers 11 to nn ) and q1,q2,,qmq_{1}, q_{2}, \ldots, q_{m} (of integers 11 to mm ). Initially pi=aip_{i}=a_{i} for i=1,2,,ni=1, 2, \ldots, n , and qj=bjq_{j} = b_{j} for j=1,2,,mj = 1, 2, \ldots, m . You can apply the following operation on the permutations several (possibly, zero) times.

In one operation, pp and qq will change according to the following three steps:

  • You choose integers ii , jj which satisfy 1in1 \le i \le n and 1jm1 \le j \le m .
  • Permutation pp is partitioned into three parts using pip_i as a pivot: the left part is formed by elements p1,p2,,pi1p_1, p_2, \ldots, p_{i-1} (this part may be empty), the middle part is the single element pip_i , and the right part is pi+1,pi+2,,pnp_{i+1}, p_{i+2}, \ldots, p_n (this part may be empty). To proceed, swap the left and the right parts of this partition. Formally, after this step, pp will become pi+1,pi+2,,pn,pi,p1,p2,,pi1p_{i+1}, p_{i+2}, \ldots, p_{n}, p_{i}, p_{1}, p_{2}, \ldots, p_{i-1} . The elements of the newly formed pp will be reindexed starting from 11 .
  • Perform the same transformation on qq with index jj . Formally, after this step, qq will become qj+1,qj+2,,qm,qj,q1,q2,,qj1q_{j+1}, q_{j+2}, \ldots, q_{m}, q_{j}, q_{1}, q_{2}, \ldots, q_{j-1} . The elements of the newly formed qq will be reindexed starting from 11 .

Your goal is to simultaneously make pi=ip_{i}=i for i=1,2,,ni=1, 2, \ldots, n , and qj=jq_{j} = j for j=1,2,,mj = 1, 2, \ldots, m .

Find any way to achieve the goal using the minimum number of operations possible, or say that none exists. Please note that you have to minimize the number of operations.

^{\dagger} A permutation of length kk is an array consisting of kk distinct integers from 11 to kk in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation ( 22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation ( k=3k=3 but there is 44 in the array).

输入格式

The first line contains two integers nn and mm ( 1n,m25001 \le n, m \le 2500 ).

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n ( 1ain1 \le a_i \le n ).

The third line contains mm integers b1,b2,,bmb_1, b_2, \ldots, b_m ( 1bim1 \le b_i \le m ).

It is guaranteed that aa and bb are permutations.

输出格式

If there is no solution, print a single integer 1-1 .

Otherwise, print an integer kk — the number of operations to perform, followed by kk lines, each containing two integers ii and jj ( 1in1 \le i \le n , 1jm1 \le j \le m ) — the integers chosen for the operation.

If there are multiple solutions, print any of them.

Please note that you have to minimize the number of operations.

输入输出样例

  • 输入#1

    3 5
    2 1 3
    5 2 1 4 3

    输出#1

    2
    3 4
    2 4
  • 输入#2

    4 4
    3 4 2 1
    2 4 1 3

    输出#2

    3
    3 3
    1 4
    4 2
  • 输入#3

    2 2
    1 2
    2 1

    输出#3

    -1

说明/提示

In the first test case, we can achieve the goal within 22 operations:

  1. In the first operation, choose i=3i = 3 , j=4j = 4 . After this, pp becomes [3,2,1][3, 2, 1] and qq becomes [3,4,5,2,1][3, 4, 5, 2, 1] .
  2. In the second operation, choose i=2i = 2 , j=4j = 4 . After this, pp becomes [1,2,3][1, 2, 3] and qq becomes [1,2,3,4,5][1, 2, 3, 4, 5] .

In the third test case, it is impossible to achieve the goal.

首页