eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Карлики

Карлики

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Давным-давно возникла большая дискуссия между гномами в Гномляндии. Правительство хотело ввести удостоверение личности для всех жителей.

Большинство гномов соглашаются быть маленькими, но они не хотят быть измеренными. Поэтому правительство позволило им заменить поле "высота гнома" в своем удостоверении личности полем "относительная высота гнома". Для изготовления удостоверений личности гномы брали интервью об их относительных размерах. По какой-то причине правительство подозревает, что по крайней мере один из опрошенных гномов возможно солгал.

Можете ли Вы помочь узнать, предполагает ли предоставленная информация существование хотя бы одного карлика сказавшего неправду?

Входные данные

Первая строка содержит количество утверждений n~(1 \le n \le 10^5). Следующие n строк описывают отношения между карликами. Каждое отношение задается строкой вида "s_1 < s_2" или "s_1 > s_2", утверждающей что карлик s_1 меньше или выше карлика s_2. s_1 и s_2 — различные имена карликов.

Имя карлика состоит из не более 20 букв от "A" до "Z" и "a" до "z". Имя карлика не содержит пробелов. Количество карликов не превосходит 10^4.

Выходные данные

Выведите "impossible" если утверждения не совместимы, иначе выведите "possible".

Пример

Входные данные #1
3
Dori > Balin
Balin > Kili
Dori < Kili
Выходные данные #1
impossible
Входные данные #2
3
Dori > Balin
Balin > Kili
Dori > Kili
Выходные данные #2
possible
Источник 2016 German Collegiate Programming Contest (GCPC), Задача A