CF939D.Love Rescue

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 nn consisting only of lowercase English letters. Using one unit of mana, grandmother can buy a spell of form (c1,c2)(c_{1},c_{2}) (where c1c_{1} and c2c_{2} are some lowercase English letters), which can arbitrary number of times transform a single letter c1c_{1} to c2c_{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.

输入格式

The first line contains a single integer nn ( 1<=n<=1051<=n<=10^{5} ) — the length of the letterings.

The second line contains a string with length nn , 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.

输出格式

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

In the next tt 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.

输入输出样例

  • 输入#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
    

说明/提示

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

首页