Problem E
First Last
Alice and Bob are playing a word game. They start with a list of words, and they alternate turns. Alice goes first; she chooses a starting word from the list. On each subsequent turn, the current player must choose a word from the list that starts with the same letter that ends the word chosen by the other player in the previous turn. No word can be used more than once. At some point one of them will not be able to choose a word; that player loses.
Assume Alice and Bob both play optimally. How many words from the list, when chosen as the first word by Alice, lead to a win for her?
Input
The first line of input contains a single integer $n$ ($1 \le n \le 1\, 000$) which is the number of words.
Each of the next $n$ lines contains a single word consisting only of the lower-case letters ‘a’ through ‘z’. Each word will be from two to fifteen letters long. All words will be distinct. There will be at most three distinct letters at the beginning and end of all words. Alice and Bob may only choose words from this list.
Output
Output a single integer, which is the number of words from the list which force a win for Alice if she chooses it first, and both Alice and Bob play optimally.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 attic climb alpha |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
22 agora alpha antic aorta apnea arena aroma attic basic blurb china circa civic climb cobra cocoa comic comma conic crumb cubic cynic |
6 |
