Gnomi#7945
Molto tempo fa, nel Paese degli Gnomi scoppiò un'accesa discussione. Il governo intendeva introdurre le carte d'identità per tutti i residenti.
La maggior parte degli gnomi era d'accordo sul fatto di essere piccoli, ma si oppose fermamente a essere misurata. In risposta alle loro proteste, il governo concesse loro di sostituire il campo "altezza dello gnomo" nella carta d'identità con un campo chiamato "altezza relativa dello gnomo". Per rilasciare queste carte d'identità, gli gnomi venivano intervistati e invitati a esprimere la propria altezza relativa rispetto agli altri. Tuttavia, per qualche motivo, il governo sospetta che almeno uno degli gnomi possa aver mentito.
Riuscite a determinare se le informazioni fornite rendono possibile che almeno uno gnomo non stia dicendo la verità?
La prima riga contiene il numero di affermazioni n~(1 \le n \le 10^5).
Ciascuna delle righe seguenti descrive una relazione tra due gnomi. Ogni affermazione è data nella forma "s_1 < s_2" oppure "s_1 > s_2", indicando che lo gnomo s_1 è più basso o più alto dello gnomo s_2, rispettivamente. Qui, s_1 e s_2 sono nomi distinti di gnomi.
Il nome di uno gnomo è composto da non più di lettere latine (maiuscole "A" — "Z" e minuscole "a" — "z"). I nomi degli gnomi non contengono spazi. Il numero totale di gnomi distinti non supera 10^4.
Stampare "impossible" se le affermazioni sono in contraddizione tra loro, altrimenti stampare "possible".
Esempio 1
Esempio 2