Cat and Mouse

A cat and a mouse play a game on an undirected tree with $N$ vertices numbered $1$ to $N$. The cat starts at vertex $1$ and the mouse starts at vertex $M$. Every edge of the tree carries cheese, and the amounts are the distinct numbers $1$ to $N-1$. The two animals move alternately, and the mouse moves first.

On its turn the mouse leaves its current vertex along the incident edge with the largest amount of cheese. If the cat stands on that neighboring vertex, the mouse leaves along the incident edge with the second largest amount of cheese instead. If there is no second vertex to move to, the game ends and the cat wins. On its turn the cat moves to a neighboring vertex or stays where it is.

You control the cat and want to win as early as possible. Find the minimum number of moves the mouse makes before the cat wins.

The first line contains the number of test cases $T$. The $T$ test cases follow.

The first line of each test case contains $N$ and $M$. Each of the next $N-1$ lines contains two integers $u$ and $v$ and describes an edge between vertex $u$ and vertex $v$. The $k$-th of these edges ($1 \le k \le N-1$) carries $k$ units of cheese.

Constraints

• $1 \le T \le 100$
• $2 \le N \le 2000$
• $1 \le M \le N$
• $1 \le u, v \le N$
• The graph of each test case is a tree.
• The sum of $N$ over all test cases is at most $5000$.
• The mouse never eats the cheese, so every edge keeps the same amount for the whole game.
• The cat may move onto the vertex that holds the mouse. The mouse takes no harm and the game simply continues.

For each test case, in the order given in the input, print one line with the minimum number of moves the mouse makes before the cat wins, assuming the cat plays optimally. Print $-1$ if the cat cannot win.