#include<bits/stdc++.h>

#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define rep(i,l,r) for(int i = l;i <= r;i ++)
#define dep(i,l,r) for(int i = l;i >= r;i --)

using namespace std;

int read(){
	int s = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
	return s * w;
}

int c,t; 
int n,m,k;
int cnt;
bool bk[100010];
int ans;

vector <int> e[1000010];
map <pair <int,int> ,int> id;

void dfs(int x,int now){
	if(now == n - 1){
		ans ++;
		return ;
	}
	for(int v : e[x]){
		if(bk[v])continue;
		bk[v] = 1;
		now ++;
		dfs(v,now);
		bk[v] = 0;
	}
}

signed main(){
	freopen("traverse.in","r",stdin);
	freopen("traverse.out","w",stdout);
	cin>>c>>t;
	if(c >= 4){
		while(t --)puts("1");
		return 0; 
	}
	cin>>n>>m;
	rep(i,1,n - 1){
		int x,y;
		x = read(),y = read();
		id[{x,y}] = ++ cnt;
	}
	for(auto now : id){
		int x = now.first.first,y = now.first.second;
		for(auto now2 : id){
			int xx = now2.first.first,yy = now2.first.second;
			if(x == xx && y == yy)continue;
			if(x == xx || x == yy || y == xx || y == yy){
				e[now.second].push_back(now2.second);
			}
		}
	}
	cin>>k;bk[k] = 1;
	dfs(k,1);
	cout<<ans;
}

/*

1 1
4 1
1 2
2 3
2 4
1

*/
