Edit Distance 다시 한 번

편집 거리(edit distance) 문제를 들어 본 적이 있는가? 영어 소문자로 이루어진 두 문자열이 주어지면, 첫 번째 문자열을 두 번째 문자열로 바꾸는 데 필요한 최소 연산 횟수를 구해야 한다. 한 번의 연산은 다음 중 하나이다.

• 수열의 임의의 위치에 문자 하나를 삽입한다.
• 수열의 임의의 문자 하나를 삭제한다.
• 문자 하나를 다른 문자로 치환한다.

우리 대학 사람들은 모두 이 문제를 아주 좋아한다. 어쩌면 조금 지나치게 좋아한다. 그래서 더 쉬운 문제를 만들기로 했다! 두 문자열 $s = s_1 \ldots s_n$, $t = t_1 \ldots t_m$과 정수 $k$가 주어진다. 두 문자열의 편집 거리가 $k$ 이하인지 판단하라. 그렇다면 $s$를 $t$로 바꾸는 최소 연산 횟수의 연산 수열도 하나 출력하라.

첫 줄에 테스트 케이스의 개수 $z$ ($1 \leq z \leq 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n, m, k$ ($1 \leq n, m \leq 1\,000\,000$, $0 \leq k \leq 1000$)가 주어진다. 이는 두 문자열의 길이와 문제에 나온 매개변수이다. 둘째 줄에는 길이 $n$의 영어 소문자로 이루어진 문자열 $s$가, 셋째 줄에는 길이 $m$의 영어 소문자로 이루어진 문자열 $t$가 주어진다.

모든 테스트 케이스의 문자열 길이 총합은 $10^7$을 넘지 않는다.

각 테스트 케이스마다 편집 거리가 $k$보다 크면 NO 한 줄을 출력한다. 그렇지 않으면 첫 줄에 YES를 출력한다. 둘째 줄에는 $s$를 $t$로 바꾸는 데 필요한 최소 연산 횟수 $r$을 출력한다. 이어서 연산을 한 줄에 하나씩 $r$줄에 걸쳐 출력한다.

• 길이 $w$인 수열의 위치 $p$ ($1 \leq p \leq w + 1$)에 영어 소문자 $c$를 삽입하려면 INSERT p c를 출력한다.
• 길이 $w$인 수열의 위치 $p$ ($1 \leq p \leq w$)에 있는 문자를 삭제하려면 DELETE p를 출력한다.
• 길이 $w$인 수열의 위치 $p$ ($1 \leq p \leq w$)에 있는 문자를 영어 소문자 $c$로 치환하려면 REPLACE p c를 출력한다.