스러피

대문자 문자열이 Slimp 뒤에 Slump가 이어지는 Slurpy인지 판별한다. 두 요소는 재귀 문법 규칙으로 정의된다.

보통5재귀문자열구현백트래킹면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

스러피(Slurpy)는 아래에서 정의하는 규칙을 만족하는 문자열이다. 문자열을 읽어 스러피인지 판정하는 프로그램을 작성한다.

먼저 스럼프(Slump)는 다음 규칙을 만족하는 문자열이다.

  1. 첫 글자는 'D' 또는 'E'이다.
  2. 첫 글자 뒤에 'F'가 한 개 이상 연달아 온다.
  3. 그 'F' 뒤에는 또 다른 스럼프가 오거나 'G' 한 글자가 온다. 따라서 스럼프는 언제나 'G'로 끝난다. 예를 들어 DFFEFFFG는 'D'로 시작해 'F'가 두 개 이어지고, 그 뒤에 또 다른 스럼프 EFFFG가 온다. 같은 규칙으로 EFFFG도 스럼프다.
  4. 위 규칙으로 만들 수 없는 문자열은 스럼프가 아니다.

스림프(Slimp)는 다음 규칙을 만족하는 문자열이다.

  1. 첫 글자는 'A'이다.
  2. 길이가 2인 스림프라면 두 번째 글자는 'H'이다.
  3. 길이가 3 이상인 스림프라면 다음 두 형태 중 하나다.
    1. 'A' + 'B' + 스림프 + 'C'
    2. 'A' + 스럼프 + 'C'
  4. 스림프의 길이는 2 이상이고, 위 규칙으로 만들 수 없는 문자열은 스림프가 아니다.

스러피는 스림프 하나 뒤에 스럼프 하나를 이어 붙인 문자열이다.

분류 예시는 다음과 같다.

  • 스럼프: DFG, EFG, DFFFFFG, DFDFDFDFG, DFEFFFFFG
  • 스럼프가 아닌 문자열: DFEFF, EFAHG, DEFG, DG, EFFFFDG
  • 스림프: AH, ABAHC, ABABAHCC, ADFGC, ADFFFFGC, ABAEFGCC, ADFDFGC
  • 스림프가 아닌 문자열: ABC, ABAH, DFGC, ABABAHC, SLIMP, ADGC
  • 스러피: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFG
  • 스러피가 아닌 문자열: AHDFGA, DFGAH, ABABCC

입력

첫 줄에 문자열의 개수 NN이 주어진다. NN1010 이하의 양의 정수다. 다음 NN개의 줄에 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 길이가 6060 이하이고 알파벳 대문자로만 이루어져 있다.

출력

첫 줄에 SLURPYS OUTPUT을 출력한다. 이어서 입력 순서대로 각 문자열이 스러피면 YES를, 스러피가 아니면 NO를 한 줄에 하나씩 출력한다. 마지막 줄에 END OF OUTPUT을 출력한다.