CF766D Mahmoud and a Dictionary

Mahmoud 想要编写一本包含 $n$ 个单词及其关系的新词典。单词之间有两种关系：同义（即两个单词含义相同）和反义（即两个单词含义相反）。他会不时发现两个单词之间有新的关系。 他知道，如果两个单词之间有关系，那么它们各自和与对方有关系的单词也有关系。例如，如果 like 的意思是 love，love 又是 hate 的反义词。那么，like 也与 hate 是反义词。再如：如果 love 是 hate 的反义词，hate 又是 like 的反义词，那么 love 和 like 就是同义词，依此类推。 有时候，Mahmoud 会发现一些错误的关系。错误的关系指的是，会导致某两个单词既是同义词又是反义词。例如：如果他已经知道 love 和 like 意思相同，like 和 hate 意思相反，然后得出 hate 和 like 意思相同，那么最后这个关系肯定是错误的，因为它会让 hate 和 like 既互为反义词又是同义词。 在 Mahmoud 发现了很多关系之后，他担心其中一些关系是错误的，这可能还会导致其他关系也变得错误。因此，他决定把每一个他发现的关系都告诉他的程序员朋友 Ehab，并且每发现一个关系就想知道，这个关系在已有关系基础上是正确还是错误的。如果是错误的，他就会忽略它，也不会在后续关系中再检查它。 等所有关系都添加完后，Mahmoud 会询问 Ehab 若干对单词之间的关系，基于之前已有的信息进行判断。Ehab 在忙着出 Codeforces 比赛题，所以让你来帮忙解答。

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$2 \leq n \leq 10^5$，$1 \leq m, q \leq 10^5$），分别表示词典中单词数、已知的关系数和需要回答的问题数。 第二行包含 $n$ 个不同的单词 $a_1, a_2, ..., a_n$，这些单词全部由小写英文字母组成，长度不超过 $20$。 接下来 $m$ 行，每行包含一个整数 $t$（$1 \leq t \leq 2$）以及两个不同的单词 $x_i$ 和 $y_i$，这两个单词都在之前的词典单词中出现过。如果 $t=1$，表示 $x_i$ 与 $y_i$ 是同义词关系；如果 $t=2$，表示 $x_i$ 与 $y_i$ 是反义词关系。 再接下来 $q$ 行，每行包含两个不同的单词，都是词典中的。表示 Mahmoud 想要询问这两个单词之间的关系。 输入中的所有单词只包含小写英文字母，长度不超过 $20$ 个字符。在所有的关系和所有的询问中，两词都不同。

首先输出 $m$ 行，每行对应一次关系的添加。如果这个关系是错误的（即导致某两个单词既是同义词又是反义词），则输出 "NO"（不带引号）并忽略此关系，否则输出 "YES"。 之后输出 $q$ 行，每行对应一次询问：若这两个单词同义，输出 $1$；若为反义词，输出 $2$；若它们没有已知关系则输出 $3$。 参见样例以便更好地理解题意。

由 ChatGPT 5 翻译