A와 C의 친족 관계를 나타내는 최대 열 개의 관계어가 주어질 때, 두 사람 사이의 친족 호칭 거리의 최댓값과 최솟값을 구한다.
어려움8그래프최단 경로완전 탐색구현아직 제출이 없습니다시간 제한8초메모리 제한512 MB사라는 책 읽기를 좋아한다. 어느 날 추리 소설에 나오는 가족의 관계가 궁금해졌다. 소설에는 이렇게 적혀 있다.
father의 brother의 son이다.aunt이다.사라는 스스로에게 물었다. "그러면 A와 C는 몇 촌일까?"
B와 C의 관계는 두 가지로 읽힌다. C는 B의 father의 여자 형제일 수도 있고, B의 mother의 여자 형제일 수도 있다. 앞의 경우 C는 A의 father의 여자 형제이므로 A와 3촌이다. 뒤의 경우 C는 A의 father의 brother의 아내의 여자 형제이므로 A와 5촌이다.
사라의 친구인 당신은 프로그래밍을 잘한다. 주어진 관계에서 A와 C의 촌수가 최대 몇이고 최소 몇인지 구하는 프로그램을 써서 사라를 도울 수 있다.
A와 C의 관계는 다음 열여섯 개 기본 관계를 이어 붙여 나타낸다: father, mother, son, daughter, husband, wife, brother, sister, grandfather, grandmother, grandson, granddaughter, uncle, aunt, nephew, niece.
각 관계의 뜻은 다음과 같다.
brother는 X의 father 또는 mother의 son 가운데 X 자신이 아닌 사람이다.grandfather는 X의 father 또는 mother의 father이다.grandson은 X의 son 또는 daughter의 son이다.uncle은 X의 father 또는 mother의 brother이다.nephew는 X의 brother 또는 sister의 son이다.sister, grandmother, granddaughter, aunt, niece도 같은 방식으로 정의한다.이 가족에는 입양, 친족 사이의 결혼(그래서 가계도에 순환이 없다), 이혼, 재혼, 중혼, 동성혼이 하나도 없다고 가정한다.
촌수는 다음과 같이 정한다.
father, mother, son, daughter 사이의 거리는 1이다.husband 또는 wife 사이의 거리는 0이다.첫 줄에 데이터 집합의 개수 T가 주어진다. (1≤T≤200)
이어지는 T개의 줄에 데이터 집합이 한 줄에 하나씩 다음 형식으로 주어진다.
C is A('s relation)*
relation은 위에 나온 열여섯 개 단어 가운데 하나이다. 별표는 괄호로 묶인 부분이 0번 이상 되풀이된다는 뜻이다. 한 데이터 집합에 들어가는 relation은 최대 열 개이다. 모든 데이터 집합에는 그 관계를 만족하는 가족이 적어도 하나 존재한다.
각 데이터 집합마다 A와 C의 촌수의 최댓값과 최솟값을 공백 하나로 구분해 한 줄에 출력한다. 다른 문자는 출력하지 않는다.