Problem C
Mårten's Theorem
According to Mårten’s Theorem, everything which rhymes is the same thing. For example, Sheep is the same thing as Heap, Dictionary Attack is the same thing as Stack, and Tree is the same thing as the Mediterranean Sea.
Strangely, some people have objected to Mårten’s Theorem, despite being rigorously proved by Johan’s infinitely many self-referencing recursive lemmas. You have been given the task of deciding if a number of statements are consistent under Mårten’s Theorem.
You will be given a number of statements of the form "$X$ is $Y$" or "$X$ not $Y$", where $X$ and $Y$ are words consisting solely of the characters ’a’-’z’, with a length of 1-20 characters, denoting that $X$ is or isn’t equivalent to $Y$. You must decide whether the statements given are consistent with each other. For example, the two statements ulf is lukas and ulf not lukas contradict each other, and are not consistent with each other.
However, you must also take Mårten’s theorem into account. For the sake of simplicity, we say that two words rhyme if the last $\min (3, |X|, |Y|)$ characters are the same in two words. So if this condition holds for two words $X$ and $Y$ that are in the list of statements, it is equivalent to having a statement "$X$ is $Y$".
Note that words which do not appear in any statement do not exist, and should not be considered rhyming with anything. That is, the two words foo and moo do not rhyme with each other, unless the word oo or o exists in the input.
Input
The first line consists of an integer $0 \le N \le 100\, 000$, the number of statements. The next $N$ lines consists of statements of the two given forms.
Output
Output should consist of the string "yes", if the statements are consistent with each other, i.e. everything which is stated to be the same either explicitly or by Mårten’s Theorem, really is the same. If you can find contradiction, output the string "wait what?".
| Sample Input 1 | Sample Output 1 |
|---|---|
4 herp is derp derp is herp herp is herp derp is derp |
yes |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 oskar not lukas oskar is poptart lukas is smart |
wait what? |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 moo not foo |
yes |
| Sample Input 4 | Sample Output 4 |
|---|---|
2 moo not foo oo is blah |
wait what? |
