ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

2159. Essay

Time limit: 2.0 second
Memory limit: 256 MB
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: s1, s2, …, sn. Secondly, it is necessary to follow k rules of the form (ai, bi) — if the word ai appears in the essay, then the word bi must necessarily appear in the essay after ai, 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: s1, s2, …, sn. It is guaranteed that all key words are distinct.
The last k lines contain one rule each: the i-th line contains two words ai bi, indicating the rule of the form (ai, bi). It is guaranteed that no two rules are the same, i.e., for any ij, either aiaj or bibj.
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.


2 3
atan ate
atan tabular
zzz atan
atan ate tabular tan
1 3
a b
b c
c a


An essay p = p1p2pa (p1, p2, …, pa are characters: letters or spaces) is lexicographically smaller than an essay q = q1q2qb (q1, q2, …, qb are also characters) if one of the following conditions is met:
  • a < b and p1 = q1, p2 = q2, …, pa = qa.
  • There exists an i such that for all j < i, pj = qj, but the character pi comes earlier in the alphabet than the character qi. 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 p1 = q1 = a, but p2 = b comes earlier in the alphabet than q2 = c.
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2021