영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Two people, let us call them Anna and Bosse, take turns saying a letter (Anna says the first letter, Bosse the second, Anna the third, and so on). The same letter may be used multiple times. There are two rules:
- The letters said so far (in order) must not form a completed word.
- The letters said so far (in order) must be able to form a word if more letters are appended at the end.
The one who breaks either rule loses, and the other one thus wins (in the real game, one can bluff on the second rule).
For example, if the letters S, T, and U have been said, then Bosse loses if he says P since STUP is a word. Furthermore, he loses if he says, e.g., J since no word starts with STUJ. However, the game continues if he says G; Anna then cannot say A since STUGA is a word, but she can say B, thereby forcing Bosse to complete the word STUGBY.
For simplicity, we assume here that only the letters A-Z may be used. Furthermore, there is a dictionary containing all letter combinations that are to be considered words in this particular game. Write a program that determines which letters are “safe” to start with for Anna, i.e., the letters that allow her to win the round regardless of which letters Bosse chooses.
Input
The first line contains an integer N (1 ≤ N ≤ 40000), the number of words in the dictionary.
Then follow N lines with one word on each line. The words are in alphabetical order and are all distinct. Each word consists of at least 1 and at most 20 letters, chosen from the uppercase letters A-Z. Made-up words may also appear.
Output
The program should output an alphabetically sorted list of the letters that have the property that, if Anna starts with the letter, she will be able to win regardless of which letters Bosse chooses (both may of course adapt their choices based on what the other says). The letters should be separated by spaces and appear on a single line.
예제
예제 1
8 FE FRI FRIA KO SE STUGA STUGBY STUP
K S