{"problem":{"name":"D. Love Rescue","description":{"content":"Valya and Tolya are an ideal pair, but they quarrel sometimes. Recently, Valya took offense at her boyfriend because he came to her in t-shirt with lettering that differs from lettering on her pullove","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF939D"},"statements":[{"statement_type":"Markdown","content":"Valya and Tolya are an ideal pair, but they quarrel sometimes. Recently, Valya took offense at her boyfriend because he came to her in t-shirt with lettering that differs from lettering on her pullover. Now she doesn't want to see him and Tolya is seating at his room and crying at her photos all day long.\n\nThis story could be very sad but fairy godmother (Tolya's grandmother) decided to help them and restore their relationship. She secretly took Tolya's t-shirt and Valya's pullover and wants to make the letterings on them same. In order to do this, for one unit of mana she can buy a spell that can change some letters on the clothes. Your task is calculate the minimum amount of mana that Tolya's grandmother should spend to rescue love of Tolya and Valya.\n\nMore formally, letterings on Tolya's t-shirt and Valya's pullover are two strings with same length _n_ consisting only of lowercase English letters. Using one unit of mana, grandmother can buy a spell of form (_c_1, _c_2) (where _c_1 and _c_2 are some lowercase English letters), which can arbitrary number of times transform a single letter _c_1 to _c_2 and vise-versa on both Tolya's t-shirt and Valya's pullover. You should find the minimum amount of mana that grandmother should spend to buy a set of spells that can make the letterings equal. In addition you should output the required set of spells.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the length of the letterings.\n\nThe second line contains a string with length _n_, consisting of lowercase English letters — the lettering on Valya's pullover.\n\nThe third line contains the lettering on Tolya's t-shirt in the same format.\n\n## Output\n\nIn the first line output a single integer — the minimum amount of mana _t_ required for rescuing love of Valya and Tolya.\n\nIn the next _t_ lines output pairs of space-separated lowercase English letters — spells that Tolya's grandmother should buy. Spells and letters in spells can be printed in any order.\n\nIf there are many optimal answers, output any.\n\n[samples]\n\n## Note\n\nIn first example it's enough to buy two spells: ('_a_','_d_') and ('_b_','_a_'). Then first letters will coincide when we will replace letter '_a_' with '_d_'. Second letters will coincide when we will replace '_b_' with '_a_'. Third letters will coincide when we will at first replace '_b_' with '_a_' and then '_a_' with '_d_'.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"瓦莉娅和托利亚是一对理想的情侣，但有时也会争吵。最近，瓦莉娅因为男友穿着的T恤上的字母与她毛衣上的字母不同而生气了，现在她不想见他，而托利亚则坐在房间里，整天对着她的照片哭泣。\n\n这个故事本可能很悲伤，但仙女教母（托利亚的奶奶）决定帮助他们，修复他们的关系。她偷偷拿走了托利亚的T恤和瓦莉娅的毛衣，想要让两件衣服上的字母相同。为了做到这一点，花费一单位魔力，她可以购买一个法术，形式为 $(c1, c2)$（其中 $c1$ 和 $c2$ 是某些小写英文字母），该法术可以任意次数地将T恤和毛衣上的单个字母 $c1$ 变为 $c2$，反之亦然。你需要计算奶奶为拯救托利亚和瓦莉娅的爱情所需花费的最少魔力值。\n\n更正式地说，托利亚的T恤和瓦莉娅的毛衣上的字母序列是两个长度均为 $n$、仅由小写英文字母组成的字符串。使用一单位魔力，奶奶可以购买一个形如 $(c1, c2)$ 的法术，该法术可以在两件衣服上任意次数地将字母 $c1$ 和 $c2$ 相互转换。你需要找到奶奶需要购买的最少魔力值，以及对应的法术集合，使得两件衣服上的字母序列完全相同。\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——字母序列的长度。\n\n第二行包含一个长度为 $n$ 的字符串，由小写英文字母组成——瓦莉娅毛衣上的字母序列。\n\n第三行包含同样格式的托利亚T恤上的字母序列。\n\n第一行输出一个整数——拯救瓦莉娅和托利亚爱情所需的最少魔力值 $t$。\n\n接下来的 $t$ 行，每行输出一对用空格分隔的小写英文字母——奶奶应购买的法术。法术和法术中的字母可以按任意顺序输出。\n\n如果有多个最优答案，输出任意一个即可。\n\n在第一个例子中，只需购买两个法术：('a','d') 和 ('b','a')。那么第一个字母可以通过将 'a' 替换为 'd' 变得相同；第二个字母可以通过将 'b' 替换为 'a' 变得相同；第三个字母则可以通过先将 'b' 替换为 'a'，再将 'a' 替换为 'd' 变得相同。\n\n## Input\n\n第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）——字母序列的长度。第二行包含一个长度为 $n$ 的字符串，由小写英文字母组成——瓦莉娅毛衣上的字母序列。第三行包含同样格式的托利亚T恤上的字母序列。\n\n## Output\n\n第一行输出一个整数——拯救瓦莉娅和托利亚爱情所需的最少魔力值 $t$。接下来的 $t$ 行，每行输出一对用空格分隔的小写英文字母——奶奶应购买的法术。法术和法术中的字母可以按任意顺序输出。如果有多个最优答案，输出任意一个即可。\n\n[samples]\n\n## Note\n\n在第一个例子中，只需购买两个法术：('a','d') 和 ('b','a')。那么第一个字母可以通过将 'a' 替换为 'd' 变得相同；第二个字母可以通过将 'b' 替换为 'a' 变得相同；第三个字母则可以通过先将 'b' 替换为 'a'，再将 'a' 替换为 'd' 变得相同。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s, t \\in \\Sigma^n $ be two strings of length $ n $, where $ \\Sigma $ is the set of lowercase English letters.  \nLet $ G = (V, E) $ be an undirected graph where $ V \\subseteq \\Sigma $ is the set of distinct letters appearing in $ s $ or $ t $, and an edge $ (c_1, c_2) \\in E $ exists if $ c_1 $ and $ c_2 $ must be made equivalent (i.e., connected via spells).\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. For all $ i \\in \\{1, \\dots, n\\} $, $ s_i, t_i \\in \\Sigma $\n\n**Objective**  \nFor each position $ i $, if $ s_i \\ne t_i $, then $ s_i $ and $ t_i $ must be in the same connected component of $ G $.  \nMinimize the number of edges $ |E| $ such that for all $ i $ with $ s_i \\ne t_i $, $ s_i $ and $ t_i $ are connected in $ G $.  \nOutput the minimum number of spells and any such minimal set of edges (spells).\n\n**Solution Formulation**  \nConstruct graph $ G $:  \n- For each $ i \\in \\{1, \\dots, n\\} $ such that $ s_i \\ne t_i $, add an undirected edge between $ s_i $ and $ t_i $.  \n- Find connected components of $ G $.  \n- For each connected component with $ k $ nodes, add $ k - 1 $ edges to form a spanning tree (minimizes spells).  \n- Output all edges from these spanning trees.\n\n**Output**  \nLet $ C_1, \\dots, C_m $ be the connected components of $ G $.  \nFor each component $ C_j $ with $ |C_j| \\geq 2 $, output $ |C_j| - 1 $ edges forming a spanning tree (e.g., connect all nodes to the first node).  \nTotal mana = total number of edges = $ \\sum_{j=1}^m \\max(0, |C_j| - 1) $.\n\n**Formal Statement**\n\nLet $ s, t \\in \\Sigma^n $ be input strings.  \nDefine edge set $ E = \\emptyset $.  \nFor $ i = 1 $ to $ n $:  \n  If $ s_i \\ne t_i $, add edge $ (s_i, t_i) $ to $ E $ (multiedges allowed, but ignored in graph).  \n\nLet $ G = (V, E) $ be the undirected graph with $ V = \\{ c \\in \\Sigma \\mid c \\text{ appears in } s \\text{ or } t \\} $.  \nLet $ \\mathcal{C} = \\{C_1, \\dots, C_m\\} $ be the connected components of $ G $.  \n\n**Objective**:  \nMinimize $ |E_{\\text{output}}| $ such that for each $ C_j \\in \\mathcal{C} $, $ E_{\\text{output}} $ contains a spanning tree of $ C_j $.  \n\n**Output**:  \n- $ |E_{\\text{output}}| = \\sum_{j=1}^m \\max(0, |C_j| - 1) $  \n- All edges of the spanning trees of each $ C_j $ (any spanning tree per component).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF939D","tags":["dfs and similar","dsu","graphs","greedy","strings"],"sample_group":[["3\nabb\ndad","2\na d\nb a"],["8\ndrpepper\ncocacola","7\nl e\ne d\nd c\nc p\np o\no r\nr a"]],"created_at":"2026-03-03 11:00:39"}}