B. Santa Claus and Keyboard Check

Codeforces

IDCF748B

Time2000ms

Memory256MB

Difficulty—

implementationstrings

English · Original

Chinese · Translation

Formal · Original

Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other's place! That is, Santa suspects that each key is either on its place, or on the place of another key, which is located exactly where the first key should be. In order to make sure that he's right and restore the correct order of keys, Santa typed his favorite patter looking only to his keyboard. You are given the Santa's favorite patter and the string he actually typed. Determine which pairs of keys could be mixed. Each key must occur in pairs **at most once**. ## Input The input consists of only two strings _s_ and _t_ denoting the favorite Santa's patter and the resulting string. _s_ and _t_ are not empty and have the same length, which is at most 1000. Both strings consist only of lowercase English letters. ## Output If Santa is wrong, and there is no way to divide some of keys into pairs and swap keys in each pair so that the keyboard will be fixed, print «_\-1_» (without quotes). Otherwise, the first line of output should contain the only integer _k_ (_k_ ≥ 0) — the number of pairs of keys that should be swapped. The following _k_ lines should contain two space-separated letters each, denoting the keys which should be swapped. All printed letters must be distinct. If there are several possible answers, print any of them. You are free to choose the order of the pairs and the order of keys in a pair. Each letter must occur at most once. Santa considers the keyboard to be fixed if he can print his favorite patter without mistakes. [samples]

圣诞老人决定拆下他的键盘进行清洁。当他把所有按键重新装回去后，他突然意识到有些按键彼此交换了位置！也就是说，圣诞老人怀疑每个按键要么在它原本的位置，要么在另一个按键的位置上，而那个按键恰好位于第一个按键应该在的位置。为了确认他的猜想并恢复按键的正确顺序，圣诞老人看着键盘打出了他最喜欢的一段文字。给你圣诞老人最喜欢的文字和他实际打出的字符串。请确定哪些按键对可能被交换了。每个按键最多只能出现在一对中。输入仅包含两个字符串 #cf_span[s] 和 #cf_span[t]，分别表示圣诞老人最喜欢的文字和实际打出的字符串。#cf_span[s] 和 #cf_span[t] 非空且长度相同，长度不超过 #cf_span[1000]。两个字符串仅由小写英文字母组成。如果圣诞老人的猜想是错误的，即无法将某些按键分成若干对，并在每对中交换按键，从而使键盘恢复正常，请输出 «_-1_»（不含引号）。否则，输出的第一行应为一个整数 #cf_span[k]（#cf_span[k ≥ 0]），表示需要交换的按键对数。接下来的 #cf_span[k] 行，每行包含两个用空格分隔的字母，表示需要交换的按键对。所有输出的字母必须互不相同。如果有多个可能的答案，输出任意一个即可。你可以自由选择按键对的顺序以及每对中两个字母的顺序。每个字母最多只能出现一次。圣诞老人认为键盘恢复正常，当且仅当他能无误地打出他最喜欢的文字。 ## Input 输入仅包含两个字符串 #cf_span[s] 和 #cf_span[t]，分别表示圣诞老人最喜欢的文字和实际打出的字符串。#cf_span[s] 和 #cf_span[t] 非空且长度相同，长度不超过 #cf_span[1000]。两个字符串仅由小写英文字母组成。 ## Output 如果圣诞老人的猜想是错误的，即无法将某些按键分成若干对，并在每对中交换按键，从而使键盘恢复正常，请输出 «_-1_»（不含引号）。否则，输出的第一行应为一个整数 #cf_span[k]（#cf_span[k ≥ 0]），表示需要交换的按键对数。接下来的 #cf_span[k] 行，每行包含两个用空格分隔的字母，表示需要交换的按键对。所有输出的字母必须互不相同。如果有多个可能的答案，输出任意一个即可。你可以自由选择按键对的顺序以及每对中两个字母的顺序。每个字母最多只能出现一次。圣诞老人认为键盘恢复正常，当且仅当他能无误地打出他最喜欢的文字。 [samples]

**Definitions** Let $ s, t \in \Sigma^* $ be two strings of equal length $ n \geq 1 $, where $ \Sigma = \{a, b, \dots, z\} $ is the set of lowercase English letters. **Constraints** 1. $ |s| = |t| \leq 1000 $ 2. For all positions $ i \in \{1, \dots, n\} $, $ s_i \neq t_i $ implies that the key $ s_i $ is swapped with the key $ t_i $. **Objective** Find a set $ P \subseteq \Sigma \times \Sigma $ of unordered pairs $ \{a, b\} $ (with $ a \neq b $) such that: - Each letter appears in at most one pair. - For all $ i \in \{1, \dots, n\} $: $$ t_i = \begin{cases} s_i & \text{if } s_i \text{ is not swapped}, \\ b & \text{if } s_i = a \text{ and } \{a, b\} \in P, \\ a & \text{if } s_i = b \text{ and } \{a, b\} \in P. \end{cases} $$ - The mapping defined by $ P $ is an *involution*: if $ \{a, b\} \in P $, then swapping $ a \leftrightarrow b $ restores $ s $ to $ t $. If no such $ P $ exists, output $-1$. Otherwise, output $ |P| $, followed by each unordered pair $ a\ b $ (order within pair does not matter) on separate lines.

Samples

Input #1

helloworld
ehoolwlroz

Output #1

3
h e
l o
d z

Input #2

hastalavistababy
hastalavistababy

Output #2

Input #3

merrychristmas
christmasmerry

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "B. Santa Claus and Keyboard Check",
    "description": {
      "content": "Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other's place! That is, Santa suspects that eac",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF748B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Santa Claus decided to disassemble his keyboard to clean it. After he returned all the keys back, he suddenly realized that some pairs of keys took each other's place! That is, Santa suspects that eac...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "圣诞老人决定拆下他的键盘进行清洁。当他把所有按键重新装回去后，他突然意识到有些按键彼此交换了位置！也就是说，圣诞老人怀疑每个按键要么在它原本的位置，要么在另一个按键的位置上，而那个按键恰好位于第一个按键应该在的位置。\n\n为了确认他的猜想并恢复按键的正确顺序，圣诞老人看着键盘打出了他最喜欢的一段文字。\n\n给你圣诞老人最喜欢的文字和他实际打出的字符串。请确定哪些按键对可能被交换了。每个按键最多只能出现...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s, t \\in \\Sigma^* $ be two strings of equal length $ n \\geq 1 $, where $ \\Sigma = \\{a, b, \\dots, z\\} $ is the set of lowercase English letters.  \n\n**Constraints**  \n1. $ |s| = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments