Bhambhani And His Girlfriends

0

0 votes
Very-Easy
Problem

Killjee's best friend has n girlfriends. He took so much pain to make n girlfriends but now there is a problem, Houses of Bhambhani's girlfriends are connected by bidirectional roads and each connection is 1 unit long.

When house of two of the girls are k unit apart they start fighting with each other.Now,Bhambhani want to find how many pair of his girlfriend will fight.

Bhambhani asked killjee for help but as you all know killjee is a big popat and he has no clue what to do.so, he is asking you all to help him.

INPUT

First line of input contain a single integer n denoting number of girlfriends Bhambhani has. Next n-1 lines contains two space separated integers u,v, denoting there is an edge between uth and vth girlfriend. Last line of input contains a single integer k as specified in the problem.

OUTPUT

Output a single integer, denoting number of pairs of bhambhani's girlfriend which are at a distance of k units.

CONSTRAINTS

n5104 1k30

Sample Input
4
1 2
2 3
1 4
1
Sample Output
3
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Bhambhani has 4 girlfriends.

1 and 2 are 1 unit apart

2 and 3 are 1 unit apart

1 and 4 are 1 unit apart

1 and 3 are 2 unit apart

2 and 4 are 2 unit apart

3 and 4 are 3 unit apart

so 3 pairs have distance less than or equal to k hence answer is 3.

Editor Image

?