애너그램 피라미드 (Hard)

20세기 신문 뒷면에는 애너그램 퍼즐이 자주 실렸다. 스도쿠만큼 인기를 끈 적은 없지만 몇 분을 보내기에는 충분한 놀이였다. 그중 하나가 애너그램 피라미드다. 단어를 위로 쌓아 올린 모양이고, 맨 아래 단어는 $N$글자, 그 위는 $N-1$글자, 다시 그 위는 $N-2$글자로 한 글자씩 짧아진다. 맨 아래 단어를 뺀 나머지는 모두 바로 아래 단어에서 글자 하나를 빼고 남은 글자를 섞어서 만든다. 위에서 아래로 적은 애너그램 피라미드의 예는 다음과 같다.

• PIN
• SNIP
• PAINS
• PIANOS

은퇴한 금융인 지노 폰지는 옛 시절을 떠올리다가 지구라트 요양원 친구들에게 돌릴 애너그램 퍼즐을 직접 만들기로 했다. 손으로 피라미드를 짜는 재미는 그대로 두고 싶었지만 중간 단어가 떠오르지 않아 막히는 일이 잦았다. 그래서 컴퓨터공학과 학생을 고용해 프로그램을 맡겼다. 이 프로그램은 사전과 맨 위 단어, 맨 아래 단어가 주어졌을 때 애너그램 피라미드를 만들 수 있는지만 알려 주면 된다.

피라미드에 쓰는 단어는 모두 사전에 있어야 한다. 맨 위 단어와 맨 아래 단어가 주어질 때, 맨 아래 단어를 바닥에 두고 맨 위 단어를 꼭대기에 두는 애너그램 피라미드가 존재하는지 판정한다. 같은 글자의 대문자와 소문자는 같은 글자로 본다.

입력에는 여러 개의 테스트 케이스가 들어 있다. 파일 끝에 도달할 때까지 모든 케이스를 처리한다.

각 테스트 케이스는 사전에 실린 단어 수 $N$ ($N < 10^6$)과 $N$개의 단어로 시작한다. 이어서 질의 수 $M$ ($M < 100$)과 $M$개의 단어 쌍이 온다. 각 쌍은 맨 위 단어, 맨 아래 단어 순서로 주어지고, 두 단어 모두 사전에 있으며 맨 위 단어가 맨 아래 단어보다 짧다.

모든 단어는 길이가 1 이상 30 이하인 영문자 문자열이다. 대문자와 소문자는 구분하지 않는다.

토큰이 나오는 순서는 다음과 같다.

N
word1
...
wordN
M
top1 bottom1
...
topM bottomM

줄 나눔이 위와 똑같다고 가정하면 안 된다. 토큰은 어떤 공백 문자로도 나뉠 수 있으므로 공백 단위로 읽는다.

각 테스트 케이스마다 먼저 Case, 공백 하나, 케이스 번호, 콜론을 차례로 이어 붙인 줄을 출력한다. 케이스 번호는 1부터 시작해 입력에 나온 순서대로 1씩 커진다.

그 다음 질의마다 한 줄씩, 애너그램 피라미드를 만들 수 있으면 yes를, 만들 수 없으면 no를 출력한다. 질의 순서는 입력에 나온 그대로 지킨다.

줄 끝에 공백을 남기지 않고, 케이스 사이에 빈 줄을 넣지 않는다.