알파벳 블록과 비밀번호

A부터 Z까지 26개 문자를 주어진 비밀번호가 연속 부분 문자열로 하나도 나타나지 않는 사전 순으로 가장 앞선 순열로 배열합니다.

어려움8백트래킹문자열 매칭트라이아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제 설명

예제3

문제

A부터 Z까지 영어 알파벳 나무 블록 26개를 한 세트로 샀다. 블록은 길쭉한 상자에 한 줄로 들어 있어서, 그대로 늘어놓으면 26글자짜리 문장처럼 읽힌다.

여러 온라인 계정에 서로 다른 비밀번호 $N$ 개를 쓰고 있는데, 이 26글자 안에 비밀번호가 우연히 그대로 들어갈까 걱정이다. 어떤 비밀번호도 연속한 부분 문자열로 나타나지 않도록 알파벳 26개를 배열할 수 있는지 판단하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 테스트 케이스가 $T$ 개 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 정수 $N$ 이 주어지고, 둘째 줄에 서로 다른 대문자 문자열 $P_1$ , $P_2$ , ..., $P_N$ 이 공백으로 구분되어 주어진다. 이 문자열이 비밀번호다.

제한

$1 \le T \le 100$
$1 \le N \le 50$
모든 $i$ 에 대해 $1 \le |P_i| \le 26$
$i \ne j$ 이면 $P_i \ne P_j$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호다.

$y$ 는 어떤 비밀번호도 연속한 부분 문자열로 포함하지 않는, A부터 Z까지 26글자의 순열이다. 조건을 만족하는 순열이 여러 개면 그중 사전순으로 가장 앞서는 것을 출력한다. 조건을 만족하는 순열이 하나도 없으면 $y$ 자리에 IMPOSSIBLE을 출력한다.