#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
const int N = 1e5 + 5;
int n, m, p;
vector<int> g[N];
bitset<N> vis;
struct Node
{
    int v, step;
};
int ans;
void handle()
{
    queue<Node> mq; // 先起点加入队列
    mq.push({1, 0});
    vis[1] = 1;
    while(mq.size())
    {
        Node t = mq.front();mq.pop();
        if(t.step == p){
            ans++;
        }
        for(auto u : g[t.v])
        {
            if(vis[u]) continue;
            vis[u]=1;
            mq.push({u, t.step + 1});

        }
    }
    cout << ans << endl;
}
void initInput()
{
    ios::sync_with_stdio(0);
    cin >> n >> m >> p;
    for(int i = 0; i < m; i++)
    {
        int u, v;cin >> u >> v;
        g[u].push_back(v),g[v].push_back(u);
    }
}
int main(void)
{
    initInput();
    handle();
    return 0;
}