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