시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB871267.895%

## 문제

We are given a set Σ of n English lowercase characters. We select k characters from Σ without repetition and arrange these k characters in alphabetical order, then we get a word of k characters, which is called a k-word. For example, let n = 5 , k = 3, and Σ = {a, b, c, d, e}. Then there are ten 3-words which are abc, abd, abe, acd, ace, ade, bcd, bce, bde, and cde. Given two distinct k-words, S and T, we want to enumerate all k-words satisfying two conditions: (C1) the first k-word is S and the last k-word is T, and (C2) the number of common characters in any two consecutive k-words is exactly k − 1. In the above example, if we enumerate all 3-words for S = abd and T = bde , then we have a list of 3- words, (abd, abe, abc, ace, bce, bcd, cde, acd, ade, bde).

Given Σ, k, n, S, and T, enumerate all k-words so that the above two conditions (C1) and (C2) are satisfied.

## 입력

Your program is to read from standard input. The input consists of three lines. The first line contains two integers, n and k, where 2 ≤ n ≤ 20 and 1 ≤ kn − 1. The second line contains a string of n characters of Σ in alphabetical order. The third line contains two distinct k-words S and T separated by a single space.

## 출력

Your program is to write to standard output. The first line contains an integer representing the number of k-words in the enumeration list which satisfies two conditions (C1) and (C2). The second line contains all k-words in the order of enumeration. If there are many solutions, print any one of the solutions. If there is no solution, print -1 only.

## 예제 입력 1

5 3
abcde
abd bde


## 예제 출력 1

10
abd abe abc ace bce bcd cde acd ade bde


## 예제 입력 2

5 1
abcde
d c


## 예제 출력 2

5
d a b e c


## 예제 입력 3

4 3
befy
efy bef


## 예제 출력 3

4
efy bey bfy bef


## 출처

• 데이터를 만든 사람: jh05013