Problem E
Shakespeare, who?
You would like to write a very special poem for your friend.
You know a list of
Your friend thinks your poem is beautiful every time some prefix of the first word in a line matches a suffix of the last word of the previous line. Further, your friend hates it if they see the same beautiful word in two consecutive lines, or if the first word of a line and the last word of the previous line share no common prefix/suffix. So you will ensure that your poem doesn’t have such lines.
More precisely, you can define the Shakespearian index of a line
What is the most beautiful poem you can write?
Input
The first line of the input contains a single integer
The next
Output
Print a single integer that is the beauty value of the most beautiful poem you can write. If you can write an infinitely beautiful poem, print “Shakespeare, who?”.
Sample Explanation
For the first sample, one possible maximally beautiful poem
(ignore punctuation) is
elephant, oh mighty elephant,
anteater, oh hungry anteater,
raccoon, oh poor raccoon!
Sample Input 1 | Sample Output 1 |
---|---|
3 raccoon elephant anteater |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
2 tractor torrent |
Shakespeare, who? |