Paladin Manao caught the trail of the ancient Book of Evil in a swampy area. This area contains n settlements numbered from 1 to n. Moving through the swamp is very difficult, so people tramped exactly n?-?1 paths. Each of these paths connects some pair of settlements and is bidirectional. Moreover, it is possible to reach any settlement from any other one by traversing one or several paths.
The distance between two settlements is the minimum number of paths that have to be crossed to get from one settlement to the other one. Manao knows that the Book of Evil has got a damage range d. This means that if the Book of Evil is located in some settlement, its damage (for example, emergence of ghosts and werewolves) affects other settlements at distance d or less from the settlement where the Book resides.
Manao has heard of m settlements affected by the Book of Evil. Their numbers are p1,?p2,?...,?pm. Note that the Book may be affecting other settlements as well, but this has not been detected yet. Manao wants to determine which settlements may contain the Book. Help him with this difficult task.
Input
The first line contains three space-separated integers n, m and d (1?≤?m?≤?n?≤?100000; 0?≤?d?≤?n?-?1). The second line contains m distinct space-separated integers p1,?p2,?...,?pm (1?≤?pi?≤?n). Then n?-?1 lines follow, each line describes a path made in the area. A path is described by a pair of space-separated integers ai and bi representing the ends of this path.
Output
Print a single number — the number of settlements that may contain the Book of Evil. It is possible that Manao received some controversial information and there is no settlement that may contain the Book. In such case, print 0.
Examples
Input
6 2 3 1 2 1 5 2 3 3 4 4 5 5 6
Output
3
Note
Sample 1. The damage range of the Book of Evil equals 3 and its effects have been noticed in settlements 1 and 2. Thus, it can be in settlements 3, 4 or 5.
#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define mod 1e9+7
#define ll long long
#define MIN -100000
#define ms memset
using namespace std;const int maxn=1e5+5;int n,m,k;
int x,y;
vector<int> edge[maxn];int dis[maxn],mark[maxn];
int dis1[maxn],dis2[maxn];
void dfs(int u,int v)
{for(int i=0;i<edge[u].size();i++){int t=edge[u][i];if(t==v) continue;dis[t]=dis[u]+1;dfs(t,u);}
}
/*
题目大意：给定一个树，和m个感染点，和距离k，
计数其到感染点最大距离不超过k的所有点的数量。技巧题。
首先以1为根节点进行dfs，
找出距离最远的感染点m1,
再以m1为根节点进行dfs，
找出最远距离的感染点m2.
然后对每个带你进行判定，
如果距离到m1和m2的距离都不超过k,
则符合要求。具体证明：
先以1为根节点。
假设我们找到了m1在其子树1中，和m2在其子树2中，
首先对于所有不在子树1和子树2的所有点，
如果存在一个距离其大于到m1，m2的距离的感染点，
那么可以肯定这个感染点不是在子树1和2中，如果在其他子树中，
则与m1到m2距离最远矛盾。。
如果在同一子树上，很显然不可能，还是与上面的一样的矛盾。如果m1子树和m2子树是一样的也无妨，同样可以简单征的。
*/int main()
{scanf("%d%d%d",&n,&m,&k);///k为其距离for(int i=0;i<m;i++){scanf("%d",&x);mark[x]=1;}for(int i=0;i<n-1;i++){scanf("%d%d",&x,&y);edge[x].push_back(y);edge[y].push_back(x);}memset(dis,0,sizeof(dis));dfs(1,-1);///求以1为根的各点到感染物的最大距离。int max1=-1,index1;for(int i=1;i<=n;i++){if(!mark[i]) continue;if(dis[i]>max1){max1=dis[i];index1=i;}}memset(dis,0,sizeof(dis));dfs(index1,-1);///对这个点再进行一次DFSmemcpy(dis1,dis,sizeof(dis));int max2=-1,index2;for(int i=1;i<=n;i++){if(!mark[i]) continue;if(dis[i]>max2){max2=dis[i];index2=i;}}memset(dis,0,sizeof(dis));dfs(index2,-1);///对这个点再进行一次DFSmemcpy(dis2,dis,sizeof(dis));int ans=0;for(int i=1;i<=n;i++)if(dis1[i]<=k&&dis2[i]<=k) ans++;printf("%d\n",ans);return 0;
}