G. Genealogy Gumbo
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You just got a new job as a Byzantine Ancestry Project Coordinator where you try to piece together ancient family trees of people long dead. Because you can no longer ask them any questions, you have to rely on documents left from that era where names are written patrilineally: ancestry is only traced by the name of someone's father. One example of such name would be "Basil, son of Alexios". You are trying to prove your research hypothesis: the entire Byzantine population is descended from just a single common ancestor.

In order to prove this hypothesis, you need to determine whether such a family tree exists: find one possible family tree with a single root. You cannot create imaginary people or construct familial relations for which there is no historical evidence. One father can have multiple children, but one child cannot have multiple fathers. It is possible that different people have the same name.

Input

The input consists of:

  • One line with an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of parental relations specified.
  • $$$n$$$ lines, each with a name of the form "$$$A$$$, son of $$$B$$$".
Each name has at most $$$20$$$ characters and consists of one English uppercase letter (A-Z), followed by only English lowercase letters (a-z).
Output

If it is possible for the given people to have a single common ancestor, output "possible". Otherwise, output "impossible".

Examples
Input
3
Jacob, son of Isaac
Isaac, son of Abraham
Ishmael, son of Abraham
Output
possible
Input
2
Basil, son of Alexios
Procopius, son of Constantine
Output
impossible
Input
3
Alvin, son of Bert
Bert, son of Charles
Charles, son of Alvin
Output
possible
Input
2
James, son of Harry
Harry, son of James
Output
possible
Input
3
Albert, son of Brent
Cody, son of Brent
Brent, son of Daniel
Output
possible
Input
3
Aaron, son of Aaron
Aaron, son of Bobby
Bobby, son of Chris
Output
possible
Input
3
Chris, son of Bobby
Bobby, son of Aaron
Aaron, son of Aaron
Output
possible