중도파
면접 대비시간 제한20초메모리 제한1024 MB
길이가 같고 서로 다른 세 문자열이 주어질 때, 알파벳 순서를 적절히 정하면 각 문자열이 세 문자열을 사전순으로 정렬했을 때 가운데에 올 수 있는지 판정한다.
문제
정확히 세 명의 후보가 선거에 출마한다. 각 후보의 이름은 영문 대문자로만 이루어진 길이 L의 문자열이며, 두 후보의 이름이 같지 않다.
이 지역에는 후보가 이름 때문에 항상 유리하거나 불리해지는 일이 없도록 하는 법이 있다. 선거가 있을 때마다 영문 알파벳의 모든 가능한 순서 중 하나가 정해지고, 그 순서에 따라 이름을 사전순으로 정렬해 투표용지에 나열한다. (투표용지에서 두 이름 중 어느 것이 먼저 오는지 판단하려면 두 이름의 첫 글자를 비교한다. 다르면 정해진 순서에서 더 앞에 오는 글자를 가진 이름이 먼저 온다. 같으면 두 번째 글자를 비교하고, 이런 식으로 계속한다.)
세 후보는 모두 "중도" 이미지를 원하기 때문에 투표용지에 나열된 세 이름 중 가운데에 오는 것이 유리하다고 생각한다. 각 후보에 대해, 그 후보의 이름이 투표용지의 세 이름 중 두 번째가 되는 영문 알파벳 순서가 적어도 하나 존재하는지 판단하라. 각 후보는 독립적으로 판단한다.
예를 들어 후보의 이름이 BCB, CAB, CBC라고 하자. 글자 D부터 Z까지는 이 이름들에 쓰이지 않으므로 A, B, C의 상대적 순서만 고려한다. 예를 들어 순서 A, B, C를 정하면 후보는 BCB, CAB, CBC 순으로 나열된다. 이는 CAB가 가운데에 올 수 있음을 보여 준다. 순서 A, C, B를 정하면 후보는 CAB, CBC, BCB 순으로 나열된다. 이는 CBC가 가운데에 올 수 있음을 보여 준다. 그러나 나머지 네 가지 순서 중 어떤 것을 골라도 BCB는 가운데에 올 수 없다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 따른다. 각 테스트 케이스의 첫 줄에는 각 후보 이름의 길이 L이 주어진다. 다음 줄에는 영문 대문자로 이루어진 서로 다른 세 문자열 Ni가 주어지며, i번째 문자열은 i번째 후보의 이름이다.
출력
각 테스트 케이스마다 Case #x: y1 y2 y3 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, 각 yi는 문제에서 설명한 대로 i번째 후보가 가운데에 올 수 있으면 YES, 아니면 NO이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ L ≤ 100.
- 모든 i에 대해 Ni의 길이는 L이다.
- i ≠ j인 모든 i, j에 대해 Ni ≠ Nj.
힌트
마지막 샘플 케이스는 Small 데이터셋에는 나오지 않는다.
샘플 케이스 #1은 문제에서 설명한 예이다.
샘플 케이스 #2에서는 A와 C의 두 가지 상대적 순서 중 어떤 것을 골라도 CA가 가운데에 온다.
샘플 케이스 #3에서는 세 글자 L, N, S의 상대적 순서에서 어느 것이 두 번째가 되는지에 따라 어떤 이름이든 가운데에 올 수 있다.