← 返回题目列表

Codeforces · 939/D

D. 爱心救援

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

Valya 和 Tolya 是一对理想的情侣,但他们有时会争吵。最近,瓦莉亚对她的男朋友感到生气,因为他穿着 T 恤来找她,上面的字母与她套头衫上的字母不同。现在她不想见到他,托利亚坐在他的房间里,整天对着她的照片哭泣。

这个故事可能非常悲伤,但仙女教母(托利亚的祖母)决定帮助他们并恢复他们的关系。她偷偷拿走了托利亚的T恤和瓦利亚的套头衫,并想让它们上的字母保持一致。为了做到这一点,她可以用一个单位的法力购买一个可以改变衣服上一些字母的咒语。你的任务是计算托利亚的祖母应该花费的最低法力来拯救托利亚和瓦利亚的爱情。

更正式地说,Tolya 的 T 恤和 Valya 的套头衫上的字母是两个长度 n 相同且仅由小写英文字母组成的字符串。使用一个单位的法力,祖母可以购买形式为 (c1, c2) 的咒语(其中 c1 和 c2 是一些小写英文字母),该咒语可以将托利亚的 T 恤和瓦利亚的套头衫上的单个字母 c1 任意次数转换为 c2,反之亦然。你应该找到祖母应该花费的最低法力来购买一套可以使字母相等的咒语。此外,你应该输出所需的法术集。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 字母的长度。

第二行包含一个长度为 n 的字符串,由小写英文字母组成——Valya 套头衫上的字母。

第三行包含 Tolya 的 T 恤上的字母,格式相同。

输出

第一行输出一个整数——拯救 Valya 和 Tolya 之爱所需的最低法力值。

在接下来的 t 行中,输出一对以空格分隔的小写英文字母 - Tolya 的祖母应该购买的咒语。咒语和咒语中的字母可以按任何顺序打印。

如果最优答案有很多,则输出任意一个。

示例

输入 #1

3
abb
dad

输出 #1

2
a d
b a

输入 #2

8
drpepper
cocacola

输出 #2

7
l e
e d
d c
c p
p o
o r
r a

注意

在第一个示例中,购买两个咒语就足够了:('a','d') 和 ('b','a')。当我们用“d”替换字母“a”时,第一个字母将重合。当我们用“a”替换“b”时,第二个字母将重合。当我们首先将“b”替换为“a”,然后将“a”替换为“d”时,第三个字母将重合。