Витя живет в Берляндии и очень хочет поступить в университет. Для этого ему нужно сдать Единый Берляндский Экзамен, а для этого нужно получить зачёт за так называемое «тотальное сочинение». Витя не силен в берляндском языке, а в сочинениях вообще профан, поэтому он обратился за помощью к Вале. Валя разузнал, по каким критериям будет осуществлена проверка тотального сочинения, и поделился ими с Витей.

Сочинением является последовательность слов (непустых последовательностей из строчных латинских букв), записанная через пробел. Например, «aba caba» или «kek» — сочинения, а «Oh yeah!» или «wrong  answer» — нет.

Для получения зачета нужно, во-первых, обязательно написать n ключевых слов: s₁, s₂, …, s_n. Во-вторых, нужно соблюдать k правил вида (a_i, b_i) — если в сочинении встречается слово a_i, то после него в сочинении должно обязательно встретиться слово b_i, не обязательно сразу за a_i. Если все эти правила соблюсти, то за сочинение гарантирован зачет.

Вите сложно это запомнить, поэтому Валя предложил ему обратиться к Вам за помощью. Помогите составить кратчайшее сочинение, которое гарантированно будет зачтено. Если среди кратчайших по длине возможно несколько вариантов, выберите лексикографически меньший (см. примечание). Учтите: возможно, что не существует ни одного сочинения, которое гарантированно будет зачтено.

В первой строке вводятся целые числа n и k — количество ключевых слов и правил, соответственно (1 ≤ n, k ≤ 100 000).

В следующих n строках вводятся по одному в строке ключевые слова s₁, s₂, …, s_n. Гарантируется, что все ключевые слова различны.

В последних k строках вводятся по одному в строке правила: в i-й строке записано через пробел два слова a_i b_i, обозначающие правило вида (a_i, b_i). Гарантируется, что никакие два правила не совпадают, то есть для любых i ≠ j верно или a_i ≠ a_j, или b_i ≠ b_j.

Гарантируется, что суммарная введённая длина всех слов не превышает 2 000 000.

В единственной строке выведите ответ на задачу: самое короткое (а среди всех самых коротких — лексикографически минимальное) сочинение, если такое существует, или −1, если не существует.

Вывод проверяется строго: между словами следует ставить единственный пробел, а вывод сочинения следует завершить единственным символом — переводом строки.

Сочинение p = p₁p₂… p_a (p₁, p₂, …, p_a — символы: буквы или пробелы) лексикографически меньше сочинения q = q₁q₂… q_b (q₁, q₂, …, q_b — тоже символы), если выполнено одно из двух:

Например p = aba лексикографически меньше сочинения q = ac, потому что p₁ = q₁ = a, но p₂ = b стоит в алфавите раньше, чем q₂ = c.