Anagram Pyramids

Time limit2sMemory limit256 MB

Summary

Decide whether dictionary words can link the base word to the apex word by deleting and rearranging one letter at each step.

Level: Medium6 of 10
Topics: Graph, BFS, String
Solved: No attempts yet

Problem

Anagram puzzles filled the back pages of newspapers in the 20th century. One of them is the anagram pyramid, a stack of words. The word at the base has $N$ letters, the word above it has $N-1$ letters, the next one has $N-2$ letters, and so on. Every word except the one at the base is formed by removing one letter from the word below it and rearranging the remaining letters.

Here is one anagram pyramid:

PIN
SNIP
PAINS
PIANOS

You are given a dictionary and two words, one for the apex and one for the base. Write a program that decides whether an anagram pyramid can be stacked with the base word at the bottom and the apex word at the top. Every word in the pyramid has to come from the dictionary.

Input

The input holds several test cases. Process it until the end of the file.

The first line of each test case has $N$ , the number of words in the dictionary ( $N < 100000$ ). Each of the next $N$ lines has one word. The line after those has $M$ , the number of queries ( $M < 10$ ). Each of the next $M$ lines has the apex word and the base word separated by one space. Both words are in the dictionary, and the apex word is shorter than the base word.

Every word is 1 to 30 letters long. The upper case and lower case forms of a letter count as the same letter.

Output

For each test case, print Case, one space, the case number, and a colon on one line. Case numbers start at 1 and run over the whole input. Then print one line per query, in input order: yes if the pyramid can be stacked, no if it cannot.

Print no trailing space on any line, and no blank line between test cases.

Examples3

Example 1

Input

8
PEN
PIN
SNIP
PINE
PAINS
SPAIN
PIANOS
SNIPER
2
PIN PIANOS
PEN SNIPER

Expected output

Case 1:
yes
no

Example 2
Input
```
2
a
ab
1
a ab
```
Expected output
```
Case 1:
yes
```

Example 3

Input

3
a
at
ate
1
a ate
3
x
xy
xyz
2
x xyz
xy xyz
4
pen
pin
snip
spin
2
pin snip
pen snip

Expected output

Case 1:
yes
Case 2:
yes
yes
Case 3:
yes
no