Однажды Макс, едва пережив очередной тяжёлый экзамен, задался вопросом — какая из дисциплин, преподаваемых в университете, является наиболее сложной?
Листая учебный план, Макс выяснил, что для изучения некоторых предметов необходимо предварительно освоить другие предметы. Так, например, чтобы изучать «Технологии программирования», нужно сдать «Основы программирования», перед «Цифровой схемотехникой» следует пройти «Электротехнику и электронику», а для «Высокопроизводительных вычислений» требуются «Алгоритмы и структуры данных» и «Машинно-ориентированное программирование».
Макс предположил, что чем больше у предмета список предварительных требований, тем сложнее этот предмет. Более формально, сложность 0 имеют предметы без предварительных требований, сложность 1 — предметы, основывающиеся хотя бы на одном предмете сложности 0, сложность 2 — предметы, основывающиеся хотя бы на одном предмете сложности 1, и так далее.
Макс уже составил список предварительных требований для всех изучаемых предметов. Помогите ему определить предмет, сложность которого является максимальной.
Первая строка содержит целое число N (1 ≤ N ≤ 104) — количество учебных предметов.
Вторая строка содержит N различных слов Si (1 ≤ |Si| ≤ 20), состоящих из строчных латинских букв и знаков подчёркивания, — названия каждого из предметов.
Третья строка содержит целое число M (0 ≤ M ≤ 105) — количество требований.
Следующие M строк описывают предварительные требования. Каждая из них содержит слова Aj и Bj и () — соответственно название предмета, который изучается ранее, и название предмета, который изучается позднее.
Выведите названия всех предметов, имеющих максимальную сложность, в алфавитном порядке.
Если сложность хотя бы одного из предметов не может быть определена, выведите Impossible.
## Входные Данные
Первая строка содержит целое число N (1 ≤ N ≤ 104) — количество учебных предметов.Вторая строка содержит N различных слов Si (1 ≤ |Si| ≤ 20), состоящих из строчных латинских букв и знаков подчёркивания, — названия каждого из предметов.Третья строка содержит целое число M (0 ≤ M ≤ 105) — количество требований.Следующие M строк описывают предварительные требования. Каждая из них содержит слова Aj и Bj и () — соответственно название предмета, который изучается ранее, и название предмета, который изучается позднее.
## Выходные Данные
Выведите названия всех предметов, имеющих максимальную сложность, в алфавитном порядке.Если сложность хотя бы одного из предметов не может быть определена, выведите Impossible.
## Примеры
Входные данные6algorithms discrete_math higher_math history prog_basics prog_technologies4discrete_math algorithmsprog_basics prog_technologiesprog_basics algorithmshigher_math discrete_mathВыходные данныеalgorithmsВходные данные4physics machine_learning electronics ai_systems2physics electronicsmachine_learning ai_systemsВыходные данныеai_systems electronics
[samples]
Let $ n, m \in \mathbb{Z} $ with $ 2 \leq n \leq 2000 $, $ 1 \leq m \leq 2000 $.
Let $ E = \{ (c_{1,i}, c_{2,i}) \mid i \in \{1, \dots, m\} \} $ be the set of daily contract pairs, where $ c_{1,i}, c_{2,i} \in \{1, \dots, n\} $, $ c_{1,i} \ne c_{2,i} $.
Let $ d_j \in \mathbb{Z}_{\geq 0} $ denote the total number of small contracts signed with company $ j \in \{1, \dots, n\} $ over the $ m $ days.
Define $ k \in \mathbb{Z}^+ $ as the number of small contracts into which each of the $ n $ large contracts was split.
**Constraints:**
1. For each $ j \in \{1, \dots, n\} $, $ d_j \leq k $ (since each company originally had one large contract, split into $ k $ small ones).
2. For each day $ i \in \{1, \dots, m\} $, the pair $ (c_{1,i}, c_{2,i}) $ is valid (distinct companies).
3. The assignment of small contracts must allow for the possibility of continuing to sign exactly two contracts per day (possibly beyond day $ m $), without exceeding the limit of $ k $ contracts per company.
**Objective:**
Find the minimal $ k \in \mathbb{Z}^+ $ such that:
- $ d_j \leq k $ for all $ j \in \{1, \dots, n\} $,
- and the multigraph $ G = (V, E) $ with $ V = \{1, \dots, n\} $ and edge multiset $ E $ (each edge corresponds to a day’s pair) can be extended to a $ k $-regular multigraph (i.e., every vertex has degree $ k $) by adding edges.
That is, find the minimal $ k \geq \max_{j} d_j $ such that $ \sum_{j=1}^n d_j $ is even and $ k \cdot n - \sum_{j=1}^n d_j $ is even and non-negative, and the graph can be completed to a $ k $-regular multigraph (which is always possible if the degree sequence is graphical and satisfies the above parity and bound conditions).
Since we only require existence of a completion, the necessary and sufficient condition is:
$$
k \geq \max_{1 \leq j \leq n} d_j \quad \text{and} \quad k \cdot n \equiv \sum_{j=1}^n d_j \pmod{2}
$$
Thus, the minimal such $ k $ is:
$$
k = \min \left\{ t \in \mathbb{Z}^+ \,\middle|\, t \geq \max_j d_j \text{ and } t \cdot n \equiv \sum_j d_j \pmod{2} \right\}
$$