{"problem":{"name":"F. Lost in Transliteration","description":{"content":"There are some ambiguities when one writes Berland names with the letters of the Latin alphabet. For example, the Berland sound _u_ can be written in the Latin alphabet as \"_u_\", and can be written a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF883F"},"statements":[{"statement_type":"Markdown","content":"There are some ambiguities when one writes Berland names with the letters of the Latin alphabet.\n\nFor example, the Berland sound _u_ can be written in the Latin alphabet as \"_u_\", and can be written as \"_oo_\". For this reason, two words \"_ulyana_\" and \"_oolyana_\" denote the same name.\n\nThe second ambiguity is about the Berland sound _h_: one can use both \"_h_\" and \"_kh_\" to write it. For example, the words \"_mihail_\" and \"_mikhail_\" denote the same name.\n\nThere are _n_ users registered on the Polycarp's website. Each of them indicated a name represented by the Latin letters. How many distinct names are there among them, if two ambiguities described above are taken into account?\n\nFormally, we assume that two words denote the same name, if using the replacements \"_u_\" \"_oo_\" and \"_h_\" \"_kh_\", you can make the words equal. One can make replacements in both directions, in any of the two words an arbitrary number of times. A letter that resulted from the previous replacement can participate in the next replacements.\n\nFor example, the following pairs of words denote the same name:\n\n*   \"_koouper_\" and \"_kuooper_\". Making the replacements described above, you can make both words to be equal: \"_koouper_\" \"_kuuper_\" and \"_kuooper_\" \"_kuuper_\".\n*   \"_khun_\" and \"_kkkhoon_\". With the replacements described above you can make both words to be equal: \"_khun_\" \"_khoon_\" and \"_kkkhoon_\" \"_kkhoon_\" \"_khoon_\".\n\nFor a given list of words, find the minimal number of groups where the words in each group denote the same name.\n\n## Input\n\nThe first line contains integer number _n_ (2 ≤ _n_ ≤ 400) — number of the words in the list.\n\nThe following _n_ lines contain words, one word per line. Each word consists of only lowercase Latin letters. The length of each word is between 1 and 20 letters inclusive.\n\n## Output\n\nPrint the minimal number of groups where the words in each group denote the same name.\n\n[samples]\n\n## Note\n\nThere are four groups of words in the first example. Words in each group denote same name:\n\n1.  \"_mihail_\", \"_mikhail_\"\n2.  \"_oolyana_\", \"_ulyana_\"\n3.  \"_kooooper_\", \"_koouper_\"\n4.  \"_hoon_\", \"_khun_\", \"_kkkhoon_\"\n\nThere are five groups of words in the second example. Words in each group denote same name:\n\n1.  \"_hariton_\", \"_kkkhariton_\", \"_khariton_\"\n2.  \"_hkariton_\"\n3.  \"_buoi_\", \"_boooi_\", \"_boui_\"\n4.  \"_bui_\"\n5.  \"_boi_\"\n\nIn the third example the words are equal, so they denote the same name.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"当使用拉丁字母书写贝兰名字时，存在一些歧义。\n\n例如，贝兰语音 _u_ 可以用拉丁字母写作 \"_u_\"，也可以写作 \"_oo_\"。因此，两个单词 \"_ulyana_\" 和 \"_oolyana_\" 表示同一个名字。\n\n第二个歧义涉及贝兰语音 _h_：可以用 \"_h_\" 或 \"_kh_\" 来书写它。例如，单词 \"_mihail_\" 和 \"_mikhail_\" 表示同一个名字。\n\n在 Polycarp 的网站上注册了 #cf_span[n] 个用户，每个用户都指定了一个由拉丁字母组成的名字。如果考虑上述两种歧义，那么其中有多少个不同的名字？\n\n形式上，我们假设两个单词表示同一个名字，当且仅当通过使用替换规则 \"_u_\"  \"_oo_\" 和 \"_h_\"  \"_kh_\"，可以将这两个单词变为相等。这些替换可以在两个单词中任意方向进行，且每个单词中可进行任意次数的替换。由前一次替换产生的字母可以参与后续的替换。\n\n例如，以下单词对表示同一个名字：\n\n给定一个单词列表，求最少需要分成多少组，使得每组中的单词都表示同一个名字。\n\n第一行包含整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 400]) —— 列表中单词的数量。\n\n接下来的 #cf_span[n] 行每行包含一个单词。每个单词仅由小写拉丁字母组成，长度在 #cf_span[1] 到 #cf_span[20] 之间（含端点）。\n\n请输出最少的分组数量，使得每组中的单词表示同一个名字。\n\n在第一个示例中，有四个单词组。每组中的单词表示同一个名字：\n\n在第二个示例中，有五个单词组。每组中的单词表示同一个名字：\n\n在第三个示例中，两个单词相等，因此表示同一个名字。\n\n## Input\n\n第一行包含整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 400]) —— 列表中单词的数量。接下来的 #cf_span[n] 行每行包含一个单词。每个单词仅由小写拉丁字母组成，长度在 #cf_span[1] 到 #cf_span[20] 之间（含端点）。\n\n## Output\n\n请输出最少的分组数量，使得每组中的单词表示同一个名字。\n\n[samples]\n\n## Note\n\n在第一个示例中，有四个单词组。每组中的单词表示同一个名字：\"_mihail_\"、\"_mikhail_\"；\"_oolyana_\"、\"_ulyana_\"；\"_kooooper_\"、\"_koouper_\"；\"_hoon_\"、\"_khun_\"、\"_kkkhoon_\"。\n\n在第二个示例中，有五个单词组。每组中的单词表示同一个名字：\"_hariton_\"、\"_kkkhariton_\"、\"_khariton_\"；\"_hkariton_\"；\"_buoi_\"、\"_boooi_\"、\"_boui_\"；\"_bui_\"；\"_boi_\"。\n\n在第三个示例中，两个单词相等，因此表示同一个名字。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of words.  \nLet $ W = \\{w_1, w_2, \\dots, w_n\\} $ be a set of strings over the lowercase Latin alphabet, where each $ w_i $ has length between 1 and 20.\n\nDefine an equivalence relation $ \\sim $ on $ W $ generated by the following rewrite rules (applicable in both directions, any number of times):  \n- $ \\texttt{\"u\"} \\leftrightarrow \\texttt{\"oo\"} $  \n- $ \\texttt{\"h\"} \\leftrightarrow \\texttt{\"kh\"} $\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 400 $  \n2. For each $ w_i \\in W $, $ 1 \\leq |w_i| \\leq 20 $, and $ w_i \\in \\{a,b,\\dots,z\\}^* $\n\n**Objective**  \nCompute the number of equivalence classes of $ W $ under $ \\sim $, i.e., the size of the quotient set $ W / \\sim $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF883F","tags":["implementation"],"sample_group":[["10\nmihail\noolyana\nkooooper\nhoon\nulyana\nkoouper\nmikhail\nkhun\nkuooper\nkkkhoon","4"],["9\nhariton\nhkariton\nbuoi\nkkkhariton\nboooi\nbui\nkhariton\nboui\nboi","5"],["2\nalex\nalex","1"]],"created_at":"2026-03-03 11:00:39"}}