Problem D
Programming Team Selection

You are a coach for a competitive learning program. It’s time for the regional competition and you have to group your students into teams. Every team needs exactly three members and every student needs to be on a team.

While choosing your teams, you must keep in mind whether particular students work well together. During the weeks and weeks of practice leading up to the competition, you have carefully observed your students working in pairs. You have made notes of which pairs work well together and which ones don’t. You are only willing to make a team of students $a$, $b$ and $c$ if $a$ and $b$ are known to work well together, $b$ and $c$ are known to work well together, and $a$ and $c$ are known to work well together.

Input

Input contains up to $10$ test cases. Each test case starts with an integer $1 \le m \le 105$, the number of pairs that work well together. This is followed by $m$ lines, each containing space-separated names of two different students that work well together. A student name is a sequence of up to $20$ upper- and lower-case letters (a–z). Each student has a unique name and every student name occurs in at least one pair. There are at most $15$ students in a test case, and the sequence of test cases ends with value of zero for $m$.

Output

For every test case, output “possible” if it’s possible to group the students into teams the way you want to. If not, output “impossible”.

8
Greg Doug
Greg Chiam
Chiam Doug
Doug Danny
Jonathan Chiam
David Danny
Danny Jonathan
Jonathan David
8
David Doug
Doug Greg
Chiam Doug
David Greg
Jonathan David
Chiam David
Danny Jonathan
David Danny
0

possible
impossible