The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 196 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

divide and conquer

dp

trees

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Book of Evil

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPaladin 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 *p*_{1}, *p*_{2}, ..., *p*_{m}. 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 *p*_{1}, *p*_{2}, ..., *p*_{m} (1 ≤ *p*_{i} ≤ *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 *a*_{i} and *b*_{i} 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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 07:23:20 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|