수열 연산

길이가 \(N\)인 수열 \(A = [A_1, A_2, \cdots, A_N]\)과 길이가 \(M\)인 수열 \(B = [B_1, B_2, \cdots, B_M]\)이 주어진다.

수열 \(A\)는 \(N\)개의 정수 \(1, 2, \cdots, N\)을 각각 정확히 한 번씩 원소로 가지는 순열이다. 수열 \(B\)의 각 원소는 \(1\) 이상 \(N\) 이하이고, 모든 원소가 서로 다르다.

여러분이 연산을 가할 수열을 \(X\)라고 하자. 처음에 수열 \(X\)는 수열 \(A\)와 동일하다. 여러분은 수열 \(X\)에 다음 두 종류의 연산을 \(0\)회 이상 원하는 만큼 수행할 수 있다.

교환 연산

\(X = [X_1, X_2, \cdots, X_K]\)라고 하자. \(1 \le i \le K - 1\)이고 \(X_i < X_{i+1}\)인 정수 \(i\)를 골라, 인접한 두 원소 \(X_i\)와 \(X_{i+1}\)의 값을 서로 바꿀 수 있다.

합치기 연산

\(X = [X_1, X_2, \cdots, X_K]\)라고 하자. \(1 \le i \le K - 1\)인 정수 \(i\)를 골라, 인접한 두 원소 \(X_i\)와 \(X_{i+1}\)을 하나의 원소 \(\min(X_i, X_{i+1})\)로 합칠 수 있다. 즉, 이 연산을 수행하면 수열 \(X\)의 길이가 \(1\) 감소한다.

주어진 연산들을 이용하여 수열 \(X\)를 수열 \(B\)와 같게 만들 수 있는지 판정하라. 만약 가능하다면, 수열 \(X\)를 수열 \(B\)로 바꾸는 연산열을 아무거나 하나 찾아라.

연산의 개수를 최소화할 필요는 없음에 유의하라.

• 주어지는 모든 수는 정수이다.
• \(1 \le M \le N \le 3000\)
• 수열 \(A\)는 \(1, 2, \cdots, N\)의 순열이다. 즉, \(\{A_1, A_2, \cdots, A_N\} = \{1, 2, \cdots, N\}\)
• 정수 \(i\) \((1 \le i \le M)\)에 대하여 \(1 \le B_i \le N\)
• \(B_1, B_2, \cdots, B_M\)의 값은 모두 서로 다르다.

첫 줄에 두 정수 \(N\)과 \(M\)이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 \(N\)개의 정수 \(A_1, A_2, \cdots, A_N\)이 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 \(M\)개의 정수 \(B_1, B_2, \cdots, B_M\)이 공백으로 구분되어 차례대로 주어진다.

수열 \(X\)를 수열 \(B\)로 만들 수 없다면, 첫 줄에 NO를 출력한다.

수열 \(X\)를 수열 \(B\)로 만들 수 있다면, 아래와 같이 출력한다. 첫 줄에 YES를 출력한다.

그다음 줄에 수행할 연산의 개수 \(Q\)를 출력한다. \(Q\)는 \(0 \le Q \le N^2\)을 만족해야 한다.

그다음 \(Q\)개의 줄에 수행할 연산을 순서대로 출력한다. 각 연산은 다음 두 형식 중 하나이다.

1 i — 수열 \(X\)의 \(i\)번째 원소와 \((i+1)\)번째 원소에 대해 교환 연산을 수행한다. 이 연산을 수행하기 직전의 수열 \(X\)의 길이를 \(K\)라고 할 때, \(1 \le i \le K - 1\)이고, 수열 \(X\)의 \(i\)번째 원소의 값이 \((i+1)\)번째 원소보다 작아야 한다.

2 i — 수열 \(X\)의 \(i\)번째 원소와 \((i+1)\)번째 원소에 대해 합치기 연산을 수행한다. 이 연산을 수행하기 직전의 수열 \(X\)의 길이를 \(K\)라고 할 때, \(1 \le i \le K - 1\)이어야 한다.

모든 위치는 해당 연산을 수행하기 직전의 수열 \(X\)를 기준으로 하며, 수열의 첫 번째 위치는 \(1\)번으로 한다. 출력한 모든 연산을 순서대로 수행한 결과는 수열 \(B\)와 정확히 같아야 한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다. 수열 \(X\)를 수열 \(B\)로 만들 수 있다면, 위 조건을 모두 만족하는 출력이 존재함을 증명할 수 있다.

anthony0506 작성

출처 KOI