

Friend ChainsTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 9798 Accepted Submission(s): 3042 Problem Description For a group of people, there is an idea that everyone is equals to or less than 6 steps away from any other person in the group, by way of introduction. So that a chain of "a friend of a friend" can be made to connect any 2 persons and it contains no more than 7 persons. For example, if XXX is YYY¡¯s friend and YYY is ZZZ¡¯s friend, but XXX is not ZZZ's friend, then there is a friend chain of length 2 between XXX and ZZZ. The length of a friend chain is one less than the number of persons in the chain. Note that if XXX is YYY¡¯s friend, then YYY is XXX¡¯s friend. Give the group of people and the friend relationship between them. You want to know the minimum value k, which for any two persons in the group, there is a friend chain connecting them and the chain's length is no more than k . Input There are multiple cases. For each case, there is an integer N (2<= N <= 1000) which represents the number of people in the group. Each of the next N lines contains a string which represents the name of one people. The string consists of alphabet letters and the length of it is no more than 10. Then there is a number M (0<= M <= 10000) which represents the number of friend relationships in the group. Each of the next M lines contains two names which are separated by a space ,and they are friends. Input ends with N = 0. Output For each case, print the minimum value k in one line. If the value of k is infinite, then print 1 instead. Sample Input
Sample Output
Source  
