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.

This 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.

More 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 (c1, c2) (where c1 and c2 are some lowercase English letters), which can arbitrary number of times transform a single letter c1 to c2 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.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the length of the letterings.

The second line contains a string with length n, consisting of lowercase English letters — the lettering on Valya's pullover.

The third line contains the lettering on Tolya's t-shirt in the same format.

Output

In the first line output a single integer — the minimum amount of mana t required for rescuing love of Valya and Tolya.

In 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.

If there are many optimal answers, output any.

Examples

Input
3
abb
dad
Output
2
a d
b a
Input
8
drpepper
cocacola
Output
7
l e
e d
d c
c p
p o
o r
r a

Note

In 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'.

题意:用最少的字母对,使得两个字符串相等。字母对之间的字母可以相互转换。

思路:每对字符之间建条边,然后跑并查集即可。

 #include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 305500
int arr[N];
int f[N];
int n;
string s1,s2;
struct str{
int x,y;
}st[N];
vector<pair<int,int> > ans;
int getf(int v){
if(v==f[v]){
return f[v];
}else{
f[v]=getf(f[v]);
return f[v];
}
}
int merge(int u,int v){
int t1=getf(u);
int t2=getf(v);
if(t1!=t2){
f[t2]=t1;
ans.push_back(make_pair(u,v));
return ;
}
return ;
}
void init(){
for(int i=;i<=+;i++)
f[i]=i;
}
signed main(){
init();
cin>>n>>s1>>s2;
int cnt=;
for(int i=;i<n;i++){
if(s1[i]==s2[i])
continue;
else{
st[cnt].x=s1[i]-'a';
st[cnt].y=s2[i]-'a';
cnt++;
st[cnt].x=s2[i]-'a';
st[cnt].y=s1[i]-'a';
cnt++;
}
}
int add=;
for(int i=;i<cnt;i++){
if(merge(st[i].x,st[i].y)){
add++;
}
}
cout<<add<<'\n';
for(int i=;i<ans.size();i++){
cout<<(char)(ans[i].first+'a')<<" "<<(char)(ans[i].second+'a')<<'\n';
}
return ;
}

最新文章

  1. HDFS Federation (读书笔记)
  2. 加载音频Audio
  3. webdriver中定位元素,报无法找到元素的问题
  4. 如何用ajax提交多组同样的数据(数组)到后台?
  5. Linux:常用快捷键
  6. Data Base MongoVue 破解治标不治本
  7. oracle PL/SQL(procedure language/SQL)程序设计
  8. snmptrap使用
  9. 高扩展的基于NIO的服务器架构(二)
  10. poj 1228 凸包
  11. [经典] 在未排序数组中返回topK大的数
  12. Android开发之Notification的简单使用
  13. JavaScript系列----一切皆是对象
  14. socket编程中客户端常用函数
  15. 女皇武则天:我不愿被 extends
  16. c# Winfrom窗体事件中启用多线程 并用子线程修改窗体里面的属性
  17. Python-面向对象简介
  18. xxl系列部署启动通用办法
  19. TP-Link 路由器配置 config.bin 解密工具 python 代码 (转载)
  20. 一种安装openslide的简易方法

热门文章

  1. SpringBoot中service注入失败(A component required a bean of type &#39;XXService&#39; that could not found)
  2. mysql创建唯一索引UNIQUE INDEX,以及报错“#失败原因: [Execute: Duplicate entry &#39;733186700&#39; for key &#39;uniq_video_id_index&#39;]”
  3. 第4章 JIT编译器
  4. Redis缓存如何保证一致性
  5. 爬虫相关--requests库
  6. js同时获取多个共同class内容标签内容集合
  7. 虹软人脸识别 - Android Camera实时人脸追踪画框适配
  8. centos7 安装jdk及mysql8
  9. nginx 作为静态资源web服务
  10. SQLSEVER刚建表时主键自增