전화번호 단어 암기

일반 전화기의 각 숫자에 다음과 같이 영어 소문자가 배정되어 있다고 하자.

1 ij   2 abc   3 def
4 gh   5 kl    6 mn
7 prs  8 tuv   9 wxy
       0 oqz

이 대응 관계를 이용하면 전화번호를 하나 이상의 영어 단어로 외울 수 있다. 단어 하나를 숫자로 바꾸려면 단어의 각 글자를 배정된 숫자로 바꾸고 이어 붙인다. 여러 단어를 사용할 때는 각 단어의 숫자 표현을 차례로 이어 붙인 문자열이 주어진 전화번호와 정확히 같아야 한다.

전화번호와 자주 사용하는 단어 목록이 주어진다. 전화번호 전체를 표현할 수 있다면, 사용하는 단어 수가 가장 적은 표현을 찾아 출력하라.

첫째 줄에 공백 없는 전화번호가 주어진다. 길이는 100 이하이다.

둘째 줄에 단어의 개수 n(1 <= n <= 50,000)이 주어진다.

다음 n개의 줄에는 공백 없는 영어 소문자 단어가 하나씩 주어진다. 각 단어의 길이는 50 이하이다. 입력 전체 크기는 300 KB 이하이다.

전화번호를 표현할 수 있으면 첫째 줄에 사용한 단어의 수 K를 출력한다. 다음 K개의 줄에는 선택한 단어를 순서대로 한 줄에 하나씩 출력한다.

표현할 방법이 없으면 첫째 줄에 0을 출력하고, 둘째 줄에 No solution.을 출력한다.