네트워크

$n$개의 노드로 이루어진 트리 형태의 네트워크가 있다. 내부 노드는 서버를, 말단(리프) 노드는 클라이언트를 나타낸다. 노드에는 $1$부터 $n$까지 번호가 매겨져 있다. 서버 중 하나인 원본 서버 $S$는 VOD(주문형 비디오) 서비스를 제공한다. 클라이언트의 서비스 품질을 보장하려면, 각 클라이언트에서 VOD 서버 $S$까지의 거리가 주어진 값 $k$를 넘지 않아야 한다. 트리에서 노드 $u$와 노드 $v$ 사이의 거리는 $u$에서 $v$로 가는 경로 위의 간선 수로 정의한다.

$S$까지의 거리가 $k$보다 큰 클라이언트들로 이루어진 공집합이 아닌 부분집합 $C$가 존재한다면, 일부 서버에 VOD 시스템의 복제본(replica)을 배치하여 모든 클라이언트가 가장 가까운 VOD 서버(원본 시스템 또는 그 복제본)로부터 거리 $k$ 이내에 있도록 해야 한다.

트리 네트워크와 VOD 시스템을 가진 서버 $S$, 그리고 양의 정수 $k$가 주어질 때, 모든 클라이언트가 원본 또는 복제본 VOD 서버 중 가장 가까운 것으로부터 거리 $k$ 이내에 있도록 하기 위해 필요한 복제본의 최소 개수를 구하라.

예를 들어 다음과 같은 트리 네트워크를 생각해 보자.

위 트리에서 클라이언트 집합은 {1, 6, 7, 8, 9, 10, 11, 13}, 서버 집합은 {2, 3, 4, 5, 12, 14}이고, 원본 VOD 서버는 노드 12에 있다.

$k = 2$일 때, 노드 12에 VOD 서버가 하나만 있으면 {6, 7, 8, 9, 10}에 속한 클라이언트들이 VOD 서버로부터 거리 $k$보다 멀리 떨어져 있으므로 서비스 품질이 보장되지 않는다. 따라서 하나 이상의 복제본이 필요하다. 노드 4에 복제본 하나를 배치하면 각 클라이언트에서 {12, 4} 중 가장 가까운 서버까지의 거리가 $2$ 이하가 된다. 이 예시에서 필요한 복제본의 최소 개수는 1이다.

입력은 표준 입력으로 주어진다. 입력은 $T$개의 테스트 케이스로 구성된다. 테스트 케이스의 수 $T$가 입력의 첫 줄에 주어진다. 각 테스트 케이스의 첫 줄에는 트리 네트워크의 노드 수를 나타내는 정수 $n$ ($3 \le n \le 1\,000$)이 주어진다. 다음 줄에는 두 정수 $s$ ($1 \le s \le n$)와 $k$ ($k \ge 1$)가 주어지며, $s$는 VOD 서버의 번호, $k$는 서비스 품질을 보장하기 위한 거리 값이다. 이어지는 $n-1$개의 줄에는 각 줄마다 트리 네트워크의 간선을 나타내는 두 노드가 주어진다.

각 테스트 케이스마다 정확히 한 줄을 표준 출력으로 출력한다. 그 줄에는 필요한 복제본의 최소 개수를 나타내는 정수를 출력한다.