단어들의 이어 붙이기

패턴이 되는 단어 $w$ 와, 비어 있지 않은 단어들로 이루어진 유한 수열 $C = (w_1, \ldots, w_k)$ 가 주어진다. 수열 $C$ 에서 몇 개의 단어를 골라, 그 단어들이 $C$ 안에서 나타나는 순서 그대로(즉 인덱스가 순증가하도록) 이어 붙였을 때 그 결과가 패턴 $w$ 와 같아지도록 만들고 싶다. 각 단어는 많아야 한 번만 사용할 수 있고, 고른 인덱스들은 반드시 강한 증가(strictly increasing) 순서여야 한다.

패턴 $w$ 와 $C$ 의 각 단어는 모두 소문자 영어 알파벳('a'부터 'z'까지)으로만 이루어지며, 발음 부호는 없고 길이는 각각 최대 150이다. 단어의 개수 $k$ 는 $1 \le k \le 200$ 을 만족한다.

예를 들어 패턴 rytter 는 $C = (\text{ry}, \text{r}, \text{yt}, \text{y}, \text{tt}, \text{t}, \text{e}, \text{te}, \text{r}, \text{er})$ 에서 인덱스 (2, 4, 5, 7, 9) 의 단어를 골라 r + y + tt + e + r 로 만들 수 있다. (1, 5, 10) 의 단어를 골라 ry + tt + er 로 만드는 것도 같은 패턴을 얻는 또 다른 방법이다.

우리는 두 가지가 궁금하다. 첫째, 그런 선택이 몇 가지나 있는가. 둘째, 그 모든 선택 중에서 사전순으로 가장 작은 선택은 무엇인가.

다음을 수행하는 프로그램을 작성하라.

• 입력에서 패턴 $w$, 단어 개수 $k$, 그리고 $C$ 의 단어들을 읽는다.
• 위 규칙에 따라 $C$ 의 단어들을 골라 이어 붙여 패턴 $w$ 를 만들 수 있는 방법이 하나도 없으면 NIE 한 단어를 출력한다.
• 방법이 존재하면, 유효한 선택의 개수(참값이 999999 이하이면 그 개수, 1000000 이상이면 1000000)를 먼저 출력하고, 이어서 사전순으로 가장 작은 유효한 선택을 골라 그 단어들의 인덱스를 증가 순서로 한 줄에 하나씩 출력한다.

인덱스 수열의 사전순 비교는 원소를 앞에서부터 하나씩 비교하여 정한다. 두 수열이 처음으로 달라지는 위치에서 더 작은 인덱스를 가진 수열이 더 작고, 한 수열이 다른 수열의 진짜 앞부분(proper prefix)이면 짧은 쪽이 더 작다.

• 첫째 줄에는 소문자 영어 알파벳으로만 이루어진 최대 150글자의 단어 하나, 곧 패턴 $w$ 가 주어진다.
• 둘째 줄에는 양의 정수 $k$ ($k \le 200$), 곧 수열 $C$ 의 단어 개수가 주어진다.
• 이어지는 $k$ 개의 줄에는 $C$ 의 단어가 순서대로 한 줄에 하나씩 주어진다. 각 단어는 비어 있지 않고 최대 150글자의 소문자 영어 알파벳으로 이루어지며, 각 줄의 첫 글자에서 시작하고 마지막 글자 바로 뒤에서 줄이 끝난다.

다음을 출력한다.

• 규칙을 지키면서 $C$ 의 단어들로 패턴을 만들 수 없으면 NIE 한 단어만 출력한다.
• 만들 수 있으면 첫째 줄에 유효한 선택의 개수를 출력한다. 이 값은 참값이 999999 이하일 때는 정확한 개수이고, 참값이 1000000 이상일 때는 정확히 1000000 이다. 이어서 사전순으로 가장 작은 유효한 선택을 이루는 단어들의 인덱스를 증가 순서로 한 줄에 하나씩 출력한다.