길이 의 문자열 가 주어진다. 는 문자 로만 이루어져 있다.
한 번의 연산으로 현재 문자열에서 서로 이웃한 두 문자를 골라 동시에 지울 수 있다. 문자를 지운 뒤에는 남은 문자들이 순서를 유지한 채 서로 붙는다.
당신은 최소 횟수의 연산을 사용하여, 남은 문자열에 문자 과 문자 이 한 번도 등장하지 않게 하려고 한다.
가능하다면 필요한 연산 횟수의 최솟값을 출력하고, 불가능하다면 을 출력하시오.
입력은 다음과 같은 형식으로 주어진다.
문자열에서 과 이 한 번도 등장하지 않게 만들 수 있다면, 필요한 연산 횟수의 최솟값을 출력한다.
불가능하다면 을 대신 출력한다.
| 3 | 27 |
| 4 | 42 | 추가 제한이 없다. |
