가족 나무
면접 대비시간 제한3초메모리 제한2048 MB
가족 나무에서 자식은 부모보다 한 단계 아래에 놓고, 같은 단계의 사진은 좌우로 옮길 수 있을 때 나무의 최소 폭을 구합니다.
문제
가족의 매년 열리는 모임에 참석하는데, 가족 수가 점점 늘어나고 있다는 것을 알게 된다. 가족 구성원 한 명 한 명의 이름과 그들이 가계의 어느 부분에 속하는지 기억하기가 어렵다. 이를 해결하려고 큰 종이 위에 가족 나무를 그리기로 한다. 가족 구성원 모두의 초상 사진을 모아 나무 모양으로 종이에 붙이는데, 자녀의 사진은 부모의 사진보다 정확히 한 단계 아래에 둔다.
사진을 종이에 붙이기 전에 필요한 종이의 양을 계산해야 한다. 환경을 생각하는 사람이라 종이 사용량을 최대한 줄이려고 한다. 같은 단계에 있는 사진을 왼쪽이나 오른쪽으로 옮겨서 나무의 너비가 줄어든다면 그렇게 해도 된다.
입력
첫 줄에 정수 하나가 주어진다. 이며, 가족 나무에 포함된 사람의 수이다.
다음 줄에는 알고 있는 가장 오래된 조상의 이름이 주어진다.
이후 개의 줄에 A - B 형식으로 입력이 주어지며, 이는 A가 B의 부모라는 뜻이다. 이 줄들은 어떤 순서로든 주어질 수 있다.
각 사람의 이름은 영어 알파벳(A-Z, a-z) 최대 20자로 이루어진다.
출력
가족 나무의 최소 너비를 초상 사진의 개수로 출력한다.