| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 10 | 3 | 3 | 100.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:
, 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".
3 Jacob, son of Isaac Isaac, son of Abraham Ishmael, son of Abraham
possible
2 Basil, son of Alexios Procopius, son of Constantine
impossible
3 Alvin, son of Bert Bert, son of Charles Charles, son of Alvin
possible
2 James, son of Harry Harry, son of James
possible
3 Albert, son of Brent Cody, son of Brent Brent, son of Daniel
possible
3 Aaron, son of Aaron Aaron, son of Bobby Bobby, son of Chris
possible
3 Chris, son of Bobby Bobby, son of Aaron Aaron, son of Aaron
possible
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2025 Preliminaries G번