問題
두 순열 p_1, p_2, ..., p_n과 q_1, q_2, ..., q_m이 있다. 초기에 p_i=a_i(1<=i<=n), q_j=b_j(1<=j<=m)이다. 당신은 아래 시행을 적절하게 하여 p_i=i(1<=i<=n), q_j=j(1<=j<=m)가 되도록 해야 한다.
한 번의 시행에서, p와 q는 다음 세 단계에 따라 변한다:
1. 당신은 1<=i<=n, 1<=j<=m을 만족하는 두 정수 i, j를 선택한다.
2. p에서 i번째 원소를 기준으로 왼쪽 부분과 오른쪽 부분을 서로 교환한다. 즉, p를 p_(i+1), p_(i+2), ..., p_n, p_i, p_1, p_2, ..., p_(i-1)로 바꾼다. 왼쪽 부분과 오른쪽 부분은 비어 있을 수도 있다. 새롭게 만들어진 p에는 인덱스 번호가 다시 부여된다.
3. 위와 마찬가지 방법으로, q에서 j번째 원소를 기준으로 왼쪽 부분과 오른쪽 부분을 서로 교환한다.
목표를 달성하는 것이 가능한지 판별하고, 가능하다면 목표를 달성하기 위한 최소 시행 횟수를 구하여라.
入力
첫 번째 줄에 n과 m이 주어진다.
두 번째 줄에 a_1, a_2, ..., a_n이 공백으로 구분되어 주어진다.
세 번째 줄에 b_1, b_2, ..., b_m이 공백으로 구분되어 주어진다.
입력되는 수는 모두 정수이며, 추가로 다음 조건을 충족한다.
- 1 <= n <= 2500
- 1 <= m <= 2500
- a_1, a_2, ..., a_n은 1, 2, ..., n의 순열이다.
- b_1, b_2, ..., b_m은 1, 2, ..., m의 순열이다.
出力
목표를 달성하는 것이 불가능하다면 -1을 출력한다.
목표를 달성하는 것이 가능하다면 최소 시행 횟수를 출력한다.
例題 #1
3 5
2 1 3
5 2 1 4 3
2
다음 방법으로 목표를 달성할 수 있다:
1) 첫 번째 시행에서 i=3, j=4를 선택한다. 시행 후 p=[3, 2, 1], q=[3, 4, 5, 2, 1]이 된다.
2) 두 번째 시행에서 i=2, j=4를 선택한다. 시행 후 p=[1, 2, 3], q=[1, 2, 3, 4, 5]가 된다.
2회 미만의 시행으로 목표를 달성할 수 없음을 증명할 수 있다.
例題 #2
4 4
3 4 2 1
2 4 1 3
3
例題 #3
2 2
1 2
2 1
-1
ログインしないとコードを書けません。