Gnomes#7945
Long ago, a fierce debate broke out in Gnomeland. The government planned to introduce identity cards for all residents.
Most gnomes agreed that they are small, but they were strongly opposed to being measured. In response to their protests, the government allowed them to replace the “gnome height” field in the identity card with a field called “relative gnome height.” To issue these identity cards, gnomes were interviewed and asked to express their relative height compared to others. However, for some reason, the government suspects that at least one of the gnomes may have lied.
Can you determine whether the provided information allows for the possibility that at least one gnome is not telling the truth?
The first line contains the number of statements n~(1 \le n \le 10^5).
Each of the following lines describes a relationship between two gnomes. Each statement is given in the form "s_1 < s_2" or "s_1 > s_2", indicating that gnome s_1 is shorter or taller than gnome s_2, respectively. Here, s_1 and s_2 are distinct gnome names.
A gnome’s name consists of no more than Latin letters (uppercase "A" — "Z" and lowercase "a" — "z"). Gnome names do not contain spaces. The total number of distinct gnomes does not exceed 10^4.
Print "impossible" if the statements contradict each other, otherwise print "possible".
Example 1
Example 2