Problem Description

Watanabe-kun works at Tenkaichi, Inc., where he uses a chat tool for communication. The chat tool has an autocomplete feature that, when you start typing an account name with @, displays a list of account names that match the prefix in lexicographical order as autocomplete suggestions.

However, Watanabe-kun often mistakenly selects @yamada instead of @yamamoto from the autocomplete suggestions. This happens because @yamada is lexicographically smaller than @yamamoto, and thus appears at the top of the suggestions when typing up to @yama.

Watanabe-kun has a special skill that allows him to freely rearrange the order of the alphabet. For example, if Watanabe-kun uses his skill to rearrange the alphabet to abcefghijklmdnopqrstuvwxyz, then m becomes smaller than d, allowing @yamamoto to be lexicographically smaller than @yamada.

You are given $N$ requirements where you need to make account name $A_i$ lexicographically smaller than account name $B_i$. Determine the order of the alphabet rearranged by Watanabe-kun's skill that satisfies all given requirements. If multiple such orders exist, find the lexicographically smallest one in the original order of the alphabet.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_N $ $ B_N $

Output Format

Output the lexicographically smallest order of the alphabet that satisfies the conditions in one line. If no such order of the alphabet exists, output -1.

Sample Input and Output

Sample Input #1

1
yamamoto yamada

Sample Output #1

abcefghijklmdnopqrstuvwxyz

Sample Input #2

3
xx xy
z w
v w

Sample Output #2

abcdefghijklmnopqrstuvxyzw

Sample Input #3

2
a b
b a

Sample Output #3

-1

Sample Input #4

1
yamamoto yama

Sample Output #4

-1

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 1000$
• $A_i\ \neq\ B_i$
• $1\ \leq\ |A_i|,\ |B_i|\ \leq\ 1000$
• $ A_i,B_i $ consist of lowercase English letters

见题面 Input 部分

见题面 Output 部分