내 사촌 오바마

버락 오바마가 미국 대통령으로 당선되었을 때, 네덜란드의 레이던(Leiden) 시는 그의 조상인 토머스 블로섬(Thomas Blossom)과 앤 엘드슨(Anne Eldson)이 1609년부터 1629년까지 이 도시에 살았다는 사실을 자랑스럽게 발표했다. 두 사람은 종교의 자유를 찾아 잉글랜드에서 네덜란드로 건너온 125명이 넘는 개신교도 가운데 일부였으며, 이들은 훗날 '필그림 파더스(Pilgrim Fathers)'로 불리게 되었다. 앞서 미국 대통령을 지낸 부시 부자(父子) 역시 바로 이 레이던 부부의 후손이다.

물론 레이던이 버락 오바마와 이런 인연을 맺은 것은 기쁜 일이지만, 이런 관계를 가진 도시가 세상에 레이던 하나뿐일 리는 없다. 모든 사람에게는 생물학적 부모가 둘 있고 한 세대가 대략 30년마다 바뀐다고 하면, 오바마에게는 17세기 초의 조상이 수천 명은 있을 것이다.

만약 오바마와 레이던의 인연이 전적으로 남성 혈통만을 따라 이어졌다면 훨씬 더 흥미로웠을 것이다. 그러나 실제로는 그렇지 않다. 오바마의 아버지는 케냐 출신이며, 토머스 블로섬과 앤 엘드슨으로 이어지는 계보는 오바마의 어머니 쪽에서 시작된다.

일반적으로 어떤 사람 $A_0$가 수 세기 전에 살았던 사람 $B_0$의 후손일 때, 두 사람을 잇는 조상 계보가 반드시 유일한 것은 아니다. 먼 친척끼리 서로 친척인 줄도 모르고 혼인하는 일이 있기 때문이다. 이런 경우, $A_0$에서 $B_0$로 이어지는 계보 가운데 여성이 가장 적게 포함된 계보를 찾는 것이 흥미로운 문제가 된다.

당신은 조상 정보 데이터베이스를 이용해 바로 이 계보를 찾아야 한다. 구체적으로는 $A_0$에서 $B_0$로 이어지는 한 조상 계보에 등장하는 여성의 최소 인원 수를 구해야 한다. 편의를 위해 데이터베이스에는 실제 이름 대신 각 개인을 $1$부터 어떤 최댓값 $N$까지의 정수로 식별한다.

입력의 첫 줄에는 정수 하나, 곧 뒤따르는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 정수 $N$이 적힌 한 줄. $2 \le N \le 100\,000$을 만족하며, 데이터베이스에 등록된 사람 수이다.
• 서로 다른 두 정수 $A_0$와 $B_0$가 적힌 한 줄. $1 \le A_0, B_0 \le N$을 만족하며, 우리가 관심 있는 두 사람의 ID 번호이다.
• $N$개의 줄. 각 줄에는 두 정수 $f$와 $m$이 있으며 $0 \le f, m \le N$을 만족한다. $i$번째 줄의 두 정수는 ID 번호가 $i$인 사람의 아버지($f$)와 어머니($m$)의 ID 번호이다. $f = 0$(또는 $m = 0$)은 그 사람의 아버지(또는 어머니)를 알 수 없음을 뜻한다.

같은 줄의 정수들은 하나의 공백으로 구분된다.

$N$개 줄에 등장하는 아버지·어머니 정보는 성별이 일관된다. 즉, 어떤 사람도 아버지이자 동시에 어머니로 등록되지 않는다. 나이 제한은 없다. 예를 들어 열 세대 차이가 나는 남자와 여자가 함께 자식을 둘 수도 있다. 물론 조상 정보에는 순환이 존재하지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 데이터베이스상 $B_0$가 $A_0$의 조상이라면, $A_0$에서 $B_0$로 이어지는 한 조상 계보에 포함되는 여성의 최소 인원 수를 출력한다. 이때 $A_0$와 $B_0$ 자신은 (둘 중 하나가 여성이더라도) 세지 않는다. 그렇지 않다면 문자열 no ancestor를 출력한다.

여기서 남성과 여성을 구분하는 것은 남성 혈통 또는 여성 혈통이라는 전통적인 관념과, 각 사람이 데이터베이스에서 아버지 또는 어머니 중 어떤 역할로 등장하는지에 따른 분류일 뿐이며, 어떤 불쾌감도 의도하지 않는다.