Welcome to ZOJ
111 - ZOJ Monthly, October 2011 - L
Re: the Princess

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Long long ago, there is a powerful kingdom lying on ACM (short for Akiba Cho Moe) land. The Princess of the kingdom is so beautiful that she would be caught by the King Devil once she went out of the castle! Because of this reason, It costs the Princess her whole time to stay at her room to post in a forum called ZOJ (short for Zodiac Otaku Jungle). One day, the Princess posted a topic in ZOJ. There are n persons, including the Princess herself, registered in ZOJ, which means that only these n persons will post in the Princess' topic.

Now we assume that:

  • Only the person who is mentioned in the signature of who post the last reply will post the next reply to the topic.
  • No one will post two replies continuously even if he mentions himself in his own signature.
  • Let Ti be the times the ith person is mentioned in last poster's signature. Then, the probability that the ith person will post the next reply is Ti / ∑Ti. Here ∑Ti represents sum of Ti from first to nth person's.
  • Everyone has only one signature. Only the person (who is mentioned in the signature of the one who posted the last reply) will post the next reply to the topic.


There are multiple cases. The first line of each test case is an integer, n (1 ≤ n ≤ 100). There are n lines followed. The ith line is in the format of "str1: str2", where str1 is the nickname of the ith person, and str2 is the ith person's signature. The first person is the Princess, who creates the new topic. All nicknames' string length are more than 0 and less than or equal to 10. The string length of signatures are more than 0 and less than or equal to 1024, which may including {' ', ',', '.', '!', '?'}. All letters in nicknames and signatures are lowercase. Each person has a different nickname from each line.

NOTE: {' ', ',', '.', '!', '?'} are delimiters. "prin!c?e,ss" should not be treated as "princess", should be treated as "prin", "c", "e", "ss"four words.


For each case, output the expectation of number of posts, rounded to 3 digits after the decimal point. Output "Infinity" if the expectation is infinite.

Sample Input

princess: princess hates devil, loves prince!
devil: i love prince!
prince: oh my god!
princess: i love prince.
i: wtf?
wtf: call me?
me: who call me?
who: i have not call you!

Sample Output


Author: YU, Xiaoyao
Submit    Status