#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mul=599,mod=1e9+9;
int n,m;
vector<int>G[500010];
ll val[500010];
int siz[500010];
void dfs(int rt,int fa)
{
    siz[rt]=1;
    vector<ll>s;
    for(int to:G[rt])
    {
        if(to==fa) continue;
        dfs(to,rt);
        s.push_back(val[to]);
        siz[rt]+=siz[to];
    }
    sort(s.begin(),s.end());
    val[rt]=131;
    for(auto x:s) val[rt]=(val[rt]*mul+x)%mod;
}
int root;
multiset<int>st;
bool check(int rt,int fa)
{
    for(int to:G[rt])
    {
        if(to==fa) continue;
        if(!st.size()) return false;
        auto it=st.lower_bound(val[to]);
        if(it==st.end()) return false;
        if(*it!=val[to]) return false;
        st.erase(it);
        if(!check(to,rt)) return false;
    }
    return true;
}
void solve1()
{
    dfs(1,0);
    for(int son:G[1])
        if(siz[son]>siz[root])
            root=son;
    for(int son:G[1])
        if(son!=root)
            st.insert(val[son]);
    if(check(root,1)&&st.empty()) cout<<1<<'\n';
    else cout<<0<<'\n';
}
int main()
{
    freopen("Decorations.in","r",stdin);
    freopen("Decorations.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int u,v; cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if(m==1)
    {
        solve1();
        return 0;
    }
    return 0;
}