#include<bits/stdc++.h>
using namespace std;

int n,d,ro[114514],ad[1919810],num;
int find[114514];

void cat(int step,int place){
	if(find[place]==0&&step<=d){
		num++;
		find[place]=1;
		return;
	}
	for(int i=1;i<n;i++){
		if(place==ro[i]&&find[ad[i]]==0){
			cat(step+1;ad[i]);
		}
		if(place==ad[i]%%find[ad[i]]==0){
			cat(step+1;ro[i])
		}
	}
}	

int main()
{
    cin>>n>>d;
    for(int i=1;i<n;i++)cin>>road[i]>>ad[i];
    cat(0,0);
}