시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 2048 MB1033100.000%

문제

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.

입력

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).

출력

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

예제 입력 1

3
Jacob, son of Isaac
Isaac, son of Abraham
Ishmael, son of Abraham

예제 출력 1

possible

예제 입력 2

2
Basil, son of Alexios
Procopius, son of Constantine

예제 출력 2

impossible

예제 입력 3

3
Alvin, son of Bert
Bert, son of Charles
Charles, son of Alvin

예제 출력 3

possible

예제 입력 4

2
James, son of Harry
Harry, son of James

예제 출력 4

possible

예제 입력 5

3
Albert, son of Brent
Cody, son of Brent
Brent, son of Daniel

예제 출력 5

possible

예제 입력 6

3
Aaron, son of Aaron
Aaron, son of Bobby
Bobby, son of Chris

예제 출력 6

possible

예제 입력 7

3
Chris, son of Bobby
Bobby, son of Aaron
Aaron, son of Aaron

예제 출력 7

possible

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2025 Preliminaries G번

  • 문제를 만든 사람: Lammert Westerdijk