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 so-called “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 (non-empty 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₁, s₂, …, 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.

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₁, s₂, …, s_n. It is guaranteed that all key words are distinct.

The last k lines contain one rule each: the i-th 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.

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.

An essay p = p₁p₂… p_a (p₁, p₂, …, p_a are characters: letters or spaces) is lexicographically smaller than an essay q = q₁q₂… q_b (q₁, q₂, …, q_b are also characters) if one of the following conditions is met:

For example, p = aba is lexicographically smaller than the essay q = ac because p₁ = q₁ = a, but p₂ = b comes earlier in the alphabet than q₂ = c.