Поликарп и его компания решили съездить в соседнее село на дискотеку.
Всего в области, в которой они живут, находится n сёл. Дорожная система между ними не слишком развита: существует только n - 1 дорога. Каждая дорога соединяет какие-то два различных села и имеет длину 1. Из любого села можно добраться до любого другого, передвигаясь по этим дорогам.
Поликарп и компания выезжают из села s и направляются в село t по кратчайшему пути. Так как они едут со своей фонотекой, они включили музыку во время поездки. Музыка из машины Поликарпа распространяется до всех сёл, расстояние до которых не более D. Расстоянием между сёлами является минимальное количество дорог на пути из одного села в другое.
Вам даны несколько пар sk и tk. Для каждой пары определите, сколько сёл услышат хотя бы какой-то фрагмент из фонотеки Поликарпа при поездке из sk в tk.
Первая строка содержит целое число n — количество сёл (1 ≤ n ≤ 2 × 105).
В следующих n - 1 строках идёт описание дорог в виде двух чисел ai и bi, означающих, что сёла с номерами ai и bi соединены дорогой (1 ≤ ai, bi ≤ n).
Следующая строка содержит два целых числа m и D (1 ≤ m ≤ 5 × 105; 0 ≤ D ≤ 2 × 105).
В следующих m строках идут пары чисел sk и tk (1 ≤ sk, tk ≤ n).
Для каждой пары sk и tk выведите в отдельной строке искомое количество сёл.
14
1 2
1 3
2 6
2 7
3 4
3 5
6 8
8 9
8 10
7 11
7 12
7 13
12 14
5 2
2 13
12 6
10 5
7 7
9 10
10
12
13
8
5
| Название |
|---|


