생체의공학

생체의공학은 생물학적 현상을 이용하여 아주 작은 규모에서 약물이나 다른 물질을 설계하려는 분야이다. 새로운 약물을 설계할 때 중요한 점은, 약물이 몸속의 올바른 수용체 세포에 결합하여 특정 반응을 일으키거나 억제하도록 만드는 것이다. 실제 생물학은 매우 복잡하므로, 여기서는 다음과 같이 단순화한 모형을 사용한다.

결합 부위(docking site)는 $n$개의 문자로 이루어진 문자열 $z$로 나타내며, 이는 연속한 $n$개 위치의 화학적 성질을 뜻한다. 우리는 주어진 기본 구성 요소들을 이어 붙여 이 부위에 결합하는 문자열을 조립하려고 한다. 구성 요소로는 $m$개의 문자열 $y_1, y_2, \dots, y_m$이 주어지며, 각 $y_i$는 $n_i$개의 문자로 이루어져 있다. 목표는 이 구성 요소들을 순서대로 골라 이어 붙였을 때 그 결과가 $z$와 정확히 같아지도록 하는 것이다. 각 구성 요소의 공급량은 무제한이므로, 같은 $y_i$를 원하는 만큼 여러 번 사용할 수 있다.

첫째 줄에 데이터 집합의 개수를 나타내는 정수 $K \ge 1$이 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

• 데이터 집합의 첫째 줄에는 사용할 수 있는 구성 요소 문자열의 개수 $m$ ($1 \le m \le 100$)이 주어진다.
• 둘째 줄에는 문자열 $z$가 주어진다. $z$의 길이는 $1$ 이상 $1000$ 이하이며, 대소문자 영문자로만 이루어진다.
• 다음 $m$개의 줄에는 각각 구성 요소 문자열 $y_i$가 하나씩 주어진다. 각 $y_i$의 길이는 $1$ 이상 $1000$ 이하이며, 대소문자 영문자로만 이루어진다.

문자열 비교는 대소문자를 구분한다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 그다음 줄에는 $z$를 조립하는 데 필요한 구성 요소의 최소 개수를 출력한다. 만약 $z$를 조립할 수 없다면 대신 Impossible을 출력한다.