Fraud Checking

Time limit1sMemory limit2048 MB

Summary

Given two code listings of n lines each, decide whether one can be turned into the other by consistent whole-word renames, and if so, print the sorted list of renames.

Level: Medium5 of 10
Topics: Hash map, String, Implementation
Solved: No attempts yet

Problem

The exam of the First Programming Course (FPC) was a success: all students have passed, with excellent grades! In fact, they did so well that it is somewhat suspicious. It is time for a fraud check, but nobody has time to sift through hundreds of code submissions by hand. You are therefore asked to find submissions that are similar in structure. Make a fraud report if the only difference between two pieces of code is the renaming of some variables.

More precisely, one piece of code is similar to another when the two can be made identical by processing a sequence of word replacements. Each word replacement replaces all occurrences of a word. A word replacement can only replace a complete word. Spaces between words and at the start or end of a line are ignored, but newlines are not. For two pieces of code to be similar, each line of the first piece must have the same number of words as the same line in the second piece.

Given two pieces of code, check whether they are similar. If they are, print a fraud report with the sorted list of word replacements.

Input

The input consists of:

A line with one integer $n$ ( $1\leq n\leq 1000$ ), the number of lines of each code submission.

$n$ lines of code for the first submission.

$n$ lines of code for the second submission.

The lines of code consist of only spaces ( ), letters from the English alphabet (A-Z and a-z), numbers (0-9), and underscores (_). Each line of code is at least 1 and at most 120 characters long, excluding the newline character.

Output

If the two pieces of code are not similar, output -1.

If the two pieces of code are similar, output:

A line containing a non-negative number $r$ , the number of word replacements.

$r$ lines, each containing one word replacement. A word replacement consists of two words separated by a space. The list must be sorted lexicographically by ASCII value.

Examples3

Example 1

Input

4
i is 42
while i
    subtract i
print i
j is 1337
while j
    add j
print j

Expected output

3
42 1337
i j
subtract add

Example 2

Input

3
ans is 42
if ans is 42
    print ans
ans is 42
if ans is not 42
    print ans

Expected output

-1

Example 3

Input

2
ans is 42
print items
ans is 42
print ans

Expected output

-1