Кефа решил отпраздновать свой первый крупный заработок походом в ресторан.
Он живет возле необычного парка. Парк представляет из себя подвешенное дерево из n вершин c корнем в вершине 1. В вершине 1 также находится дом Кефы. К сожалению для нашего героя, в парке также находятся коты. Кефа уже выяснил номера вершин, в которых находятся коты.
В листовых вершинах парка находятся рестораны. Кефа хочет выбрать ресторан, в который он пойдет, но, к сожалению, он очень боится котов, поэтому он ни за что не пойдёт в ресторан, на пути к которому от его дома найдётся более m подряд идущих вершин с котами.
Ваша задача — помочь Кефе посчитать количество ресторанов, в которые он может сходить.
Выходные данные
Одно целое число — количество различных листьев дерева, на пути от дома Кефы до которых не больше m подряд идущих вершин с котами.
Примечание
Напомним, что дерево — это связный граф на n вершинах, состоящий из n - 1 ребра. Подвешенное дерево — это дерево с особой выделенной вершиной, корнем. В подвешенном дереве из любых двух вершин, соединённых ребром, одна называется предком (та из них, что ближе к корню), а оставшаяся — ребёнком. Вершина называется листом, если у неё нет детей.
Пояснение к первому тесту из условия: 
Красным цветом отмечены вершины в которых находятся коты. Рестораны находятся в вершинах 2, 3, 4. Кефа не может сходить только в ресторан, находящийся в вершине 2.
Пояснение ко второму тесту из условия: 
Рестораны находятся в вершинах 4, 5, 6, 7. Кефа не может попасть в рестораны 6, 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
1 1 0 0
1 2
1 3
1 4
|
2
|
|
2
|
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
|
2
|