Longest Word Sequence

You are given a set of unique words and a list of valid adjacent word pairs. Two words are considered adjacent if they appear as a pair in the given list. The relation is bidirectional, meaning if (a, b) is given it implies you can go from a to b and from b to a. Your task is to determine the maximum possible length of a sequence where every consecutive pair of words is connected by a valid pair, and no word appears more than once in the sequence. In other words, you are to find the longest path in an undirected graph where each vertex (word) is visited at most once.

The input consists of several test cases. For each test case, output the maximum sequence length in a separate line.

inputFormat

Input is given via standard input (stdin). It contains multiple test cases. Each test case starts with two integers n and m separated by space, where n is the number of words and m is the number of valid adjacent pairs. The next n lines each contain a word. The following m lines each contain two words separated by a space representing a valid adjacent pair. The input terminates with a test case where n = 0 and m = 0; this test case should not be processed.

outputFormat

For each test case, output the maximum possible sequence length (an integer) on a new line to standard output (stdout).## sample

5 4
a
b
c
d
e
a b
b c
c d
d e
4 2
x
y
z
w
x y
y z
0 0

5
3