My Cousin Obama

When Barack Obama was elected President of the United States, the city of Leiden proudly announced that his ancestors Thomas Blossom and Anne Eldson had lived there between 1609 and 1629. They were among more than 125 Protestants who had fled England for Holland in search of religious freedom, and who later became known as the Pilgrim Fathers. The Bushes, father and son, both earlier Presidents of the USA, descended from the very same Leiden couple.

Of course we are glad for Leiden that it has such a tie to Barack Obama, but Leiden is probably not the only city in the world with a connection like this. Since every person has two biological parents, and a new generation appears roughly every thirty years, Barack Obama likely has several thousand ancestors from the early seventeenth century.

It would be far more remarkable if Obama's tie to Leiden ran entirely along the male line of ancestry. That is not the case here: Obama's father is from Kenya, and the line back to Thomas Blossom and Anne Eldson runs through Obama's mother.

In general, when a person $A_0$ descends from a person $B_0$ who lived centuries ago, the line of ancestry between them need not be unique. Distant relatives may marry without ever realizing they are related. When that happens, it becomes interesting to find the line of ancestry from $A_0$ to $B_0$ that contains as few women as possible.

Your task is to do exactly this, using a database of ancestry information. Specifically, you must report the smallest number of women that appear on a line of ancestry from $A_0$ to $B_0$. For simplicity the database stores no real names; instead every individual is identified by an integer between $1$ and some maximum $N$.

The first line of the input contains a single integer: the number of test cases that follow. Each test case has the following format.

• One line with an integer $N$ satisfying $2 \le N \le 100,000$: the number of persons in the database.
• One line with two different integers $A_0$ and $B_0$ satisfying $1 \le A_0, B_0 \le N$: the ID numbers of the two persons we care about.
• $N$ lines, each with two integers $f$ and $m$ satisfying $0 \le f, m \le N$. The integers on line $i$ are the ID numbers of the father ($f$) and the mother ($m$) of the person with ID number $i$. A value $f = 0$ (or $m = 0$) means the father (or mother) of person $i$ is unknown.

Integers on the same line are separated by single spaces.

The father and mother entries across the $N$ lines are gender-consistent: no individual is registered as a father and as a mother at the same time. There are no age limits; for instance, a man and a woman ten generations apart may have a child together. The ancestry information never describes a cycle.

For each test case, print a single line. If $B_0$ is an ancestor of $A_0$ according to the database, the line contains the smallest number of women on a line of ancestry from $A_0$ to $B_0$ (not counting $A_0$ and $B_0$ themselves, even if either of them is a woman). Otherwise the line contains the string no ancestor.

Distinguishing men from women here reflects only the traditional notion of a strictly male or female line of ancestry, together with the classification of each person by the role (father or mother) in which they appear in the database. No offense is intended.