가계도

오늘날 뉴질랜드 사람의 혈통에는 마오리, 태평양 섬, 여러 서유럽 국가, 때로는 동남아시아까지 섞여 있다. 가계 자료가 충분하다면 한 사람의 혈통이 어느 쪽에서 얼마나 왔는지 알아내는 일은 어렵지 않아 보인다. 하지만 세상은 그렇게 단순한 적이 없었고, 두 사람을 놓고 실제로 알아낼 수 있는 값은 앞 세대의 사람이 뒤 세대의 사람에게 기여한 정도뿐이다. 기여가 아예 없기도 하다. 이 값을 구하는 프로그램을 작성하라.

한 사람은 두 부모에게서 각각 정확히 절반씩 혈통을 물려받는다. 따라서 조상이 후손에게 기여한 비율은 두 사람을 잇는 혈통 경로마다 $(1/2)^k$를 구해 모두 더한 값이다. $k$는 그 경로가 지나는 세대 수다.

입력은 가계도와 그 가계도에 대한 질의가 번갈아 나오는 형태다.

가계도는 # 하나만 있는 줄이 나올 때까지 이어지는 줄의 나열이다. 각 줄에는 서로 다른 이름 세 개가 공백으로 구분되어 있고, 차례로 한 사람과 그 사람의 두 부모를 뜻한다. 이름은 알파벳 20자 미만이다. 어떤 이름도 줄의 첫 번째 자리에는 많아야 한 번 나오므로 모든 사람의 부모는 0명 아니면 2명이다. 순환도 없다. 즉 자기 자신의 조상인 사람은 없다.

가계도 다음에는 질의가 이어지고, 이 부분도 # 하나만 있는 줄로 끝난다. 각 질의는 이름 두 개로 이루어진다. 이 이름은 가계도에 나오지 않을 수도 있다.

마지막에 # 하나만 있는 줄이 와서 입력이 끝난다.

질의마다 한 줄씩 출력한다.

질의에 나온 두 사람 중 한쪽이 다른 쪽의 후손이면 후손의 이름, 공백, is, 공백, 기약분수로 나타낸 혈통 비율, 공백, 조상의 이름을 차례로 출력하고 마침표 .를 찍는다.

그렇지 않으면 주어진 순서 그대로 두 이름을 넣어 A and B are not related. 형식으로 출력한다. 두 이름이 같은 경우와 한쪽 또는 양쪽이 가계도에 나오지 않는 경우가 여기에 해당한다.

앞 가계도의 답과 다음 가계도의 답 사이에는 빈 줄을 하나 넣는다.