Picture by YannGar
of a car and a bar. Which is the same thing.
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
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
is $Y$" or "$X$ not
$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
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.
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 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
herp is derp
derp is herp
herp is herp
derp is derp
|Sample Input 2
||Sample Output 2
oskar not lukas
oskar is poptart
lukas is smart
|Sample Input 3
||Sample Output 3
moo not foo
|Sample Input 4
||Sample Output 4
moo not foo
oo is blah