Vitya lives in Berland and really wants to get into university. To do this, he needs to pass the Unified Berland Exam, and for that, he needs to pass the socalled “total essay”. Vitya is not strong in the Berland language, and he is a complete amateur in essays, so he asked Valya to help. Valya found out the criteria for checking the total essay and shared them with Vitya.
An essay is a sequence of words (nonempty sequences of lowercase Latin letters) written with spaces. For example, «aba caba
» or «kek
» are essays, while «Oh yeah!
» or «wrong answer
» are not.
To pass, it is necessary, firstly, to write n key words: s_{1}, s_{2}, …, s_{n}. Secondly, it is necessary to follow k rules of the form (a_{i}, b_{i}) — if the word a_{i} appears in the essay, then the word b_{i} must necessarily appear in the essay after a_{i}, not necessarily immediately after it. If all these rules are followed, the essay is guaranteed to pass.
It is difficult for Vitya to remember all this, so Valya suggested that he seek help from you. Help him compose the shortest essay that will be guaranteed to pass. If there are several options among the shortest essays, choose the lexicographically smallest one (see note). Note that there may not be any essays that are guaranteed to pass.
Input
The first line contains two integers n and k  the number of key words and rules, respectively (1 ≤ n, k ≤ 100 000).
The next n lines contain one key word each: s_{1}, s_{2}, …, s_{n}. It is guaranteed that all key words are distinct.
The last k lines contain one rule each: the ith line contains two words a_{i} b_{i}, indicating the rule of the form (a_{i}, b_{i}). It is guaranteed that no two rules are the same, i.e., for any i ≠ j, either a_{i} ≠ a_{j} or b_{i} ≠ b_{j}.
It is guaranteed that the total length of all words does not exceed 2 000 000.
Output
In a single line, output the answer to the problem: the shortest (and among the shortest, the lexicographically smallest) essay, if it exists, or −1 if it does not exist.
The output is checked strictly: there should be a single space between words, and the output of the essay should end with a single newline character.
Samples
input  output 

2 3
atan
tan
atan ate
atan tabular
zzz atan
 atan ate tabular tan

1 3
a
a b
b c
c a
 1

Notes
An essay p = p_{1}p_{2}… p_{a} (p_{1}, p_{2}, …, p_{a} are characters: letters or spaces) is lexicographically smaller than an essay q = q_{1}q_{2}… q_{b} (q_{1}, q_{2}, …, q_{b} are also characters) if one of the following conditions is met:
 a < b and p_{1} = q_{1}, p_{2} = q_{2}, …, p_{a} = q_{a}.
 There exists an i such that for all j < i, p_{j} = q_{j}, but the character p_{i} comes earlier in the alphabet than the character q_{i}. It is considered that the space comes before all letters of the Latin alphabet.
For example, p = aba
is lexicographically smaller than the essay q = ac
because p_{1} = q_{1} = a
, but p_{2} = b
comes earlier in the alphabet than q_{2} = c
.
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2021