Гноми#7945

Гноми

1 секунда

128 мегабайтів

Дуже легка

Давним-давно в Країні Гномів спалахнула запекла суперечка. Уряд планував запровадити посвідчення особи для всіх мешканців.

Більшість гномів погоджувалися з тим, що вони маленькі, але були категорично проти того, щоб їх вимірювали. У відповідь на їхні протести уряд дозволив замінити поле «зріст гнома» в посвідченні особи на поле під назвою «відносний зріст гнома». Для оформлення цих посвідчень особи гномів опитували та просили висловити свій відносний зріст порівняно з іншими. Однак, з якоїсь причини, уряд підозрює, що принаймні один із гномів міг збрехати.

Чи можете ви визначити, чи допускає надана інформація можливість того, що принаймні один гном говорить неправду?

Вхідні дані

Перший рядок містить кількість тверджень $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5).

Кожен із наступних $n$ рядків описує відношення між двома гномами. Кожне твердження задано у вигляді " $s_{1} < s_{2}$ s_1 < s_2" або " $s_{1} > s_{2}$ s_1 > s_2", що означає, що гном $s_{1}$ s_1 нижчий або вищий за гнома $s_{2}$ s_2 відповідно. Тут $s_{1}$ s_1 та $s_{2}$ s_2 — різні імена гномів.

Ім'я гнома складається не більше ніж із $20$ латинських літер (великих "A" — "Z" та малих "a" — "z"). Імена гномів не містять пробілів. Загальна кількість різних гномів не перевищує $1 0^{4}$ 10^4.

Вихідні дані

Виведіть "impossible", якщо твердження суперечать одне одному, інакше виведіть "possible".

Приклади

Приклад 1

Приклад 2