← 返回题目列表

Codeforces · 766/D

D. 马哈茂德和一本字典

中文机器翻译题面 查看原题

Mahmoud 想要编写一本新字典,其中包含 n 个单词以及它们之间的关系。有两种类型的关系:同义(即两个词的意思相同)和反义(即两个词的意思相反)。他时不时地发现两个词之间的新关系。

他知道如果两个词之间有关系,那么它们中的每一个都与另一个词有关系。例如,如果喜欢意味着爱,而爱是恨的反义词,那么喜欢也是恨的反义词。再举个例子:如果爱是恨的反面,恨是喜欢的反面,那么爱就意味着喜欢,等等。

有时,马哈茂德会发现错误的关系。错误关系是指两个词同时相等且相反的关系。例如,如果他知道爱意味着喜欢,而喜欢与恨相反,然后他发现恨意味着喜欢,那么最后一个关系绝对是错误的,因为它使恨和喜欢相反,同时具有相同的含义。

Mahmoud 弄清楚了许多关系后,他担心其中一些关系是错误的,从而导致其他关系也错误,因此他决定将他弄清楚的每一个关系告诉他的程序员朋友 Ehab,并且根据之前发现的关系,对于每一个他想知道的关系是正确还是错误。如果错误,他会忽略它,并且不会检查以下关系。

添加完所有关系后,Mahmoud 根据 Ehab 提供的信息向 Ehab 询问一些单词之间的关系。 Ehab 正忙着举办 Codeforces 活动,因此他向您寻求帮助。

输入

输入的第一行包含三个整数 n、m 和 q (2 ≤ n ≤ 105, 1 ≤ m, q ≤ 105),其中 n 是字典中的单词数,m 是 Mahmoud 弄清楚的关系数,q 是 Mahmoud 在说出所有关系后提出的问题数。

第二行包含n个不同的单词a1,a2,...,由长度不超过20的小英文字母组成,是字典中的单词。

接下来是 m 行,每行包含一个整数 t (1 ≤ t ≤ 2),后面跟着两个不同的单词 xi 和 yi,这两个单词已经出现在字典单词中。如果t=1,则xi与yi具有同义关系,否则xi与yi具有反义关系。

接下来是q行,每行包含两个不同的单词,这些单词已经出现在字典中。这是马哈茂德想要根据他发现的关系了解它们之间的关系的词对。

输入的所有单词仅包含小写英文字母,且长度不超过20个字符。在所有关系和所有问题中,这两个词都是不同的。

输出

首先,打印 m 行,每个关系一行。如果某些关系是错误的(使两个单词相反并且同时具有相同的含义),您应该打印“NO”(不带引号)并忽略它,否则打​​印“YES”(不带引号)。

之后打印 q 行,每个问题一行。如果两个词含义相同,则输出1。如果相反,则输出2。如果没有关系,则输出3。

请参阅示例以更好地理解。

示例

输入 #1

3 3 4
hate love like
1 love like
2 love hate
1 hate like
love like
love hate
like hate
hate like

输出 #1

YES
YES
NO
1
2
2
2

输入 #2

8 6 5
hi welcome hello ihateyou goaway dog cat rat
1 hi welcome
1 ihateyou goaway
2 hello ihateyou
2 hi goaway
2 hi hello
1 hi hello
dog cat
dog hi
hi hello
ihateyou goaway
welcome ihateyou

输出 #2

YES
YES
YES
YES
NO
YES
3
3
1
1
2