Network

Consider a tree network with $n$ nodes, where the internal nodes are servers and the terminal (leaf) nodes are clients. The nodes are numbered from $1$ to $n$. Among the servers there is an original server $S$ that provides a VOD (Video On Demand) service. To guarantee the quality of service for the clients, the distance from each client to the VOD server $S$ must not exceed a given value $k$. The distance between a node $u$ and a node $v$ in the tree is the number of edges on the path from $u$ to $v$.

If there is a nonempty subset $C$ of clients whose distance to $S$ is greater than $k$, then replicas of the VOD system must be placed on some servers so that every client is within distance $k$ of the nearest VOD server (the original system or a replica).

Given a tree network, the server $S$ that holds the VOD system, and a positive integer $k$, find the minimum number of replicas needed so that every client is within distance $k$ of the nearest server that holds the original VOD system or a replica.

For example, consider the following tree network.

In this tree the set of clients is {1, 6, 7, 8, 9, 10, 11, 13}, the set of servers is {2, 3, 4, 5, 12, 14}, and the original VOD server is at node 12.

For $k = 2$, a single VOD server at node 12 does not guarantee the quality of service, because the clients in {6, 7, 8, 9, 10} are farther than $k$ from it. Therefore one or more replicas are needed. Placing one replica at node 4 makes the distance from every client to the nearest server in {12, 4} at most $2$. For this example the minimum number of replicas needed is one.

The input is read from standard input. It consists of $T$ test cases. The number of test cases $T$ is given on the first line. The first line of each test case contains an integer $n$ ($3 \le n \le 1\,000$), the number of nodes in the tree network. The next line contains two integers $s$ ($1 \le s \le n$) and $k$ ($k \ge 1$), where $s$ is the VOD server and $k$ is the distance value for guaranteeing the quality of service. Each of the following $n-1$ lines contains a pair of nodes describing an edge of the tree network.

Write to standard output. For each test case, print exactly one line containing a single integer: the minimum number of replicas needed.