{"raw_statement":[{"iden":"statement","content":"Mahmoud wants to write a new dictionary that contains _n_ words and relations between them. There are two types of relations: synonymy (i. e. the two words mean the same) and antonymy (i. e. the two words mean the opposite). From time to time he discovers a new relation between two words.\n\nHe know that if two words have a relation between them, then each of them has relations with the words that has relations with the other. For example, if _like_ means _love_ and _love_ is the opposite of _hate_, then _like_ is also the opposite of _hate_. One more example: if _love_ is the opposite of _hate_ and _hate_ is the opposite of _like_, then _love_ means _like_, and so on.\n\nSometimes Mahmoud discovers a wrong relation. A wrong relation is a relation that makes two words equal and opposite at the same time. For example if he knows that _love_ means _like_ and _like_ is the opposite of _hate_, and then he figures out that _hate_ means _like_, the last relation is absolutely wrong because it makes _hate_ and _like_ opposite and have the same meaning at the same time.\n\nAfter Mahmoud figured out many relations, he was worried that some of them were wrong so that they will make other relations also wrong, so he decided to tell every relation he figured out to his coder friend Ehab and for every relation he wanted to know is it correct or wrong, basing on the previously discovered relations. If it is wrong he ignores it, and doesn't check with following relations.\n\nAfter adding all relations, Mahmoud asked Ehab about relations between some words based on the information he had given to him. Ehab is busy making a Codeforces round so he asked you for help."},{"iden":"input","content":"The first line of input contains three integers _n_, _m_ and _q_ (2 ≤ _n_ ≤ 105, 1 ≤ _m_, _q_ ≤ 105) where _n_ is the number of words in the dictionary, _m_ is the number of relations Mahmoud figured out and _q_ is the number of questions Mahmoud asked after telling all relations.\n\nThe second line contains _n_ distinct words _a_1, _a_2, ..., _a__n_ consisting of small English letters with length not exceeding 20, which are the words in the dictionary.\n\nThen _m_ lines follow, each of them contains an integer _t_ (1 ≤ _t_ ≤ 2) followed by two different words _x__i_ and _y__i_ which has appeared in the dictionary words. If _t_ = 1, that means _x__i_ has a synonymy relation with _y__i_, otherwise _x__i_ has an antonymy relation with _y__i_.\n\nThen _q_ lines follow, each of them contains two different words which has appeared in the dictionary. That are the pairs of words Mahmoud wants to know the relation between basing on the relations he had discovered.\n\nAll words in input contain only lowercase English letters and their lengths don't exceed 20 characters. In all relations and in all questions the two words are different."},{"iden":"output","content":"First, print _m_ lines, one per each relation. If some relation is wrong (makes two words opposite and have the same meaning at the same time) you should print \"_NO_\" (without quotes) and ignore it, otherwise print \"_YES_\" (without quotes).\n\nAfter that print _q_ lines, one per each question. If the two words have the same meaning, output 1. If they are opposites, output 2. If there is no relation between them, output 3.\n\nSee the samples for better understanding."},{"iden":"examples","content":"Input\n\n3 3 4\nhate love like\n1 love like\n2 love hate\n1 hate like\nlove like\nlove hate\nlike hate\nhate like\n\nOutput\n\nYES\nYES\nNO\n1\n2\n2\n2\n\nInput\n\n8 6 5\nhi welcome hello ihateyou goaway dog cat rat\n1 hi welcome\n1 ihateyou goaway\n2 hello ihateyou\n2 hi goaway\n2 hi hello\n1 hi hello\ndog cat\ndog hi\nhi hello\nihateyou goaway\nwelcome ihateyou\n\nOutput\n\nYES\nYES\nYES\nYES\nNO\nYES\n3\n3\n1\n1\n2"}],"translated_statement":[{"iden":"statement","content":"Mahmoud 想要编写一个包含 #cf_span[n] 个单词及其相互关系的新词典。关系有两种类型：同义（即两个词含义相同）和反义（即两个词含义相反）。他不时会发现两个词之间的新关系。\n\n他知道，如果两个词之间存在某种关系，那么每个词都会与另一个词所关联的词具有相同的关系。例如，如果 _like_ 表示 _love_，而 _love_ 与 _hate_ 相反，那么 _like_ 也与 _hate_ 相反。另一个例子：如果 _love_ 与 _hate_ 相反，而 _hate_ 与 _like_ 相反，那么 _love_ 就与 _like_ 同义，依此类推。\n\n有时 Mahmoud 会发现一个错误的关系。错误的关系是指使两个词同时成为同义且反义的关系。例如，如果他知道 _love_ 与 _like_ 同义，而 _like_ 与 _hate_ 相反，然后他又发现 _hate_ 与 _like_ 同义，那么这个新关系绝对是错误的，因为它使 _hate_ 和 _like_ 同时成为反义且同义。\n\n在 Mahmoud 发现了许多关系后，他担心其中一些是错误的，从而导致其他关系也出错，因此他决定将每个发现的关系告诉他的程序员朋友 Ehab，并希望对每个关系判断它是正确还是错误，依据是之前已发现的关系。如果错误，他就忽略它，不再用它检查后续关系。\n\n在添加所有关系后，Mahmoud 向 Ehab 询问某些词之间的关系，基于他提供的信息。Ehab 忙于制作 Codeforces 比赛，因此他请你帮忙。\n\n输入的第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[q]（#cf_span[2 ≤ n ≤ 105]，#cf_span[1 ≤ m, q ≤ 105]），其中 #cf_span[n] 是词典中的单词数，#cf_span[m] 是 Mahmoud 发现的关系数，#cf_span[q] 是 Mahmoud 在告知所有关系后提出的问题数。\n\n第二行包含 #cf_span[n] 个互不相同的单词 #cf_span[a1, a2, ..., an]，由长度不超过 #cf_span[20] 的小写英文字母组成，这些是词典中的单词。\n\n接下来 #cf_span[m] 行，每行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 2]），后跟两个不同的单词 #cf_span[xi] 和 #cf_span[yi]，这两个词均出现在词典中。如果 #cf_span[t = 1]，表示 #cf_span[xi] 与 #cf_span[yi] 是同义关系；否则，#cf_span[xi] 与 #cf_span[yi] 是反义关系。\n\n然后是 #cf_span[q] 行，每行包含两个不同的词，这两个词均出现在词典中，表示 Mahmoud 想要根据已发现的关系查询它们之间关系的词对。\n\n输入中的所有单词仅包含小写英文字母，长度不超过 #cf_span[20] 个字符。在所有关系和所有问题中，两个词均不同。\n\n首先，输出 #cf_span[m] 行，每行对应一个关系。如果某个关系是错误的（使两个词同时成为反义且同义），请输出 \"_NO_\"（不含引号）并忽略它；否则输出 \"_YES_\"（不含引号）。\n\n然后输出 #cf_span[q] 行，每行对应一个问题。如果两个词含义相同，输出 #cf_span[1]；如果它们是反义词，输出 #cf_span[2]；如果它们之间无任何关系，输出 #cf_span[3]。\n\n请参考样例以获得更好的理解。"},{"iden":"input","content":"The first line of input contains three integers #cf_span[n], #cf_span[m] and #cf_span[q] (#cf_span[2 ≤ n ≤ 105], #cf_span[1 ≤ m, q ≤ 105]) where #cf_span[n] is the number of words in the dictionary, #cf_span[m] is the number of relations Mahmoud figured out and #cf_span[q] is the number of questions Mahmoud asked after telling all relations.The second line contains #cf_span[n] distinct words #cf_span[a1, a2, ..., an] consisting of small English letters with length not exceeding #cf_span[20], which are the words in the dictionary.Then #cf_span[m] lines follow, each of them contains an integer #cf_span[t] (#cf_span[1 ≤ t ≤ 2]) followed by two different words #cf_span[xi] and #cf_span[yi] which has appeared in the dictionary words. If #cf_span[t = 1], that means #cf_span[xi] has a synonymy relation with #cf_span[yi], otherwise #cf_span[xi] has an antonymy relation with #cf_span[yi].Then #cf_span[q] lines follow, each of them contains two different words which has appeared in the dictionary. That are the pairs of words Mahmoud wants to know the relation between basing on the relations he had discovered.All words in input contain only lowercase English letters and their lengths don't exceed #cf_span[20] characters. In all relations and in all questions the two words are different."},{"iden":"output","content":"First, print #cf_span[m] lines, one per each relation. If some relation is wrong (makes two words opposite and have the same meaning at the same time) you should print \"_NO_\" (without quotes) and ignore it, otherwise print \"_YES_\" (without quotes).After that print #cf_span[q] lines, one per each question. If the two words have the same meaning, output #cf_span[1]. If they are opposites, output #cf_span[2]. If there is no relation between them, output #cf_span[3].See the samples for better understanding."},{"iden":"examples","content":"Input3 3 4hate love like1 love like2 love hate1 hate likelove likelove hatelike hatehate likeOutputYESYESNO1222Input8 6 5hi welcome hello ihateyou goaway dog cat rat1 hi welcome1 ihateyou goaway2 hello ihateyou2 hi goaway2 hi hello1 hi hellodog catdog hihi helloihateyou goawaywelcome ihateyouOutputYESYESYESYESNOYES33112"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ G = (V, E) $ be a graph where $ V $ is the set of $ n $ dictionary words.\n\nEach edge $ (u, v) \\in E $ is labeled with a weight $ w(u, v) \\in \\{0, 1\\} $, where:\n- $ w(u, v) = 0 $ denotes synonymy (same meaning),\n- $ w(u, v) = 1 $ denotes antonymy (opposite meaning).\n\nWe maintain a disjoint-set union (DSU) data structure with **union-find with parity tracking** (also known as DSU with \"enemy\" or \"bipartite\" extension), where each node $ u $ has an associated **parity** $ p(u) \\in \\{0, 1\\} $, representing its relative meaning with respect to its root.\n\nFor each relation $ (t, x, y) $:\n- If $ t = 1 $: enforce $ p(x) \\oplus p(y) = 0 $ (same parity).\n- If $ t = 2 $: enforce $ p(x) \\oplus p(y) = 1 $ (different parity).\n\nLet $ \\text{find}(u) $ return the root of $ u $ and its accumulated parity $ \\delta_u $ from $ u $ to root.\n\nFor a new relation $ (t, x, y) $:\n1. Compute $ r_x = \\text{find}(x) $, $ \\delta_x $, $ r_y = \\text{find}(y) $, $ \\delta_y $.\n2. If $ r_x = r_y $:\n   - Check if $ \\delta_x \\oplus \\delta_y \\equiv t - 1 \\pmod{2} $.\n   - If **not**, the relation is **invalid** → output \"NO\".\n   - Otherwise, it is consistent → output \"YES\".\n3. If $ r_x \\ne r_y $:\n   - Union the two components: set parent of $ r_y $ to $ r_x $, and assign $ \\text{parity}[r_y] = \\delta_x \\oplus \\delta_y \\oplus (t - 1) $.\n   - Output \"YES\".\n\nAfter processing all $ m $ relations, for each query $ (x, y) $:\n1. Compute $ r_x = \\text{find}(x) $, $ \\delta_x $, $ r_y = \\text{find}(y) $, $ \\delta_y $.\n2. If $ r_x \\ne r_y $: output 3 (no relation).\n3. Else: \n   - If $ \\delta_x \\oplus \\delta_y = 0 $: output 1 (synonym).\n   - If $ \\delta_x \\oplus \\delta_y = 1 $: output 2 (antonym).\n\n---\n\n**Formal Summary:**\n\n**Input:**\n- $ n $: number of words.\n- $ m $: number of relations.\n- $ q $: number of queries.\n- $ V = \\{v_1, v_2, \\dots, v_n\\} $: set of distinct words.\n- $ R = \\{(t_i, x_i, y_i)\\}_{i=1}^m $: relations, $ t_i \\in \\{1,2\\} $, $ x_i, y_i \\in V $, $ x_i \\ne y_i $.\n- $ Q = \\{(u_j, v_j)\\}_{j=1}^q $: queries, $ u_j, v_j \\in V $, $ u_j \\ne v_j $.\n\n**Data Structure:**\n- DSU with path compression and union by rank.\n- For each node $ u $, store $ \\text{parent}[u] $ and $ \\text{parity}[u] \\in \\{0,1\\} $: the XOR-sum from $ u $ to its root.\n\n**Operations:**\n- $ \\text{find}(u) $: returns $ (r, \\delta) $, where $ r $ is root, $ \\delta = \\bigoplus_{w \\in \\text{path}(u \\to r)} \\text{edge\\_weight}(w, \\text{parent}[w]) $.\n- $ \\text{union}(x, y, \\text{target}) $: where $ \\text{target} = t - 1 $, and $ t \\in \\{1,2\\} $.\n\n**For each relation $ (t, x, y) $:**\n- Let $ \\text{target} = t - 1 $.\n- $ (r_x, \\delta_x) = \\text{find}(x) $, $ (r_y, \\delta_y) = \\text{find}(y) $.\n- If $ r_x = r_y $:\n  - If $ \\delta_x \\oplus \\delta_y \\ne \\text{target} $: output \"NO\".\n  - Else: output \"YES\".\n- Else:\n  - $ \\text{parent}[r_y] = r_x $\n  - $ \\text{parity}[r_y] = \\delta_x \\oplus \\delta_y \\oplus \\text{target} $\n  - Output \"YES\".\n\n**For each query $ (x, y) $:**\n- $ (r_x, \\delta_x) = \\text{find}(x) $, $ (r_y, \\delta_y) = \\text{find}(y) $.\n- If $ r_x \\ne r_y $: output 3.\n- Else:\n  - If $ \\delta_x \\oplus \\delta_y = 0 $: output 1.\n  - Else: output 2.","simple_statement":null,"has_page_source":false}