#include<bits/stdc++.h>
using namespace std;
// #define LOCAL
#define ll long long
#define db double
#define Ciallo true
#define pir pair <ll,ll>
#define fs first
#define sc second
#define MAXN 2010
#define mod 998244353
inline ll read(){
    ll f = 1, num = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c=='-') f = -1;c = getchar();
    }
    while(c>='0'&&c<='9') num = num * 10 + c - '0', c = getchar();
    return num * f;
}

vector <int> e[MAXN * 2];
int res[MAXN * 2];
int hd[MAXN],ed[MAXN * 2], nxt[MAXN * 2];
int idx = 1;
int dfn[MAXN],lst[MAXN];
int st[MAXN],tp;
int tmp, cnt;
int n,m,k;

void add(int x, int y){
    ++ idx;
    nxt[idx] = hd[x];
    hd[x] = idx;
    ed[idx] = y;
}

void clear(int y){
    ++ cnt;
    while(tp){
        int x = st[tp];
        -- tp;
        e[x].push_back(n + cnt);
        e[n + cnt].push_back(x);
        if(x == y)return;
    }
}

void Tarjan(int x, int frm){
    lst[x] = dfn[x] = ++tmp;
    st[++ tp] = x;
    for(int i = hd[x]; i; i = nxt[i]){
        if((i ^ 1) == frm)continue;
        int y = ed[i];
        if(!dfn[y]){
            Tarjan(y, i);
            if(lst[y] >= dfn[x]){
                clear(y);
                e[x].push_back(n + cnt);
                e[n + cnt].push_back(x);
            }else lst[x] = min(lst[x], lst[y]);
            
        }else{
            lst[x] = min(lst[x], dfn[y]);
        }
    }
    // cerr << x << " " << dfn[x] << " " << lst[x] << endl;
}

int siz[MAXN * 2];
int rot,mu;
int fa[MAXN * 2];

void getrot(int x, int p){
    if(x <= n)siz[x] = 1;
    else siz[x] = 0;
    int u = 0;
    for(auto y : e[x]){
        if(y == p)continue;
        getrot(y, x);
        siz[x] += siz[y];
        u = max(u, siz[y]);
    }
    u = max(u, n - siz[x]);
    if(u < mu){
        mu = u, rot = x;
    }
}

void getsiz(int x, int p){
    if(x <= n)siz[x] = 1;
    else siz[x] = 0;
    fa[x] = p;
    for(auto y : e[x]){
        if(y == p)continue;
        getsiz(y, x);
        siz[x] += siz[y];
    }
} 

bool chk0(int s){
    for(int i = 1;i <= n; ++i){
        if(siz[i] < s)continue;
        int res = 1;
        for(auto y : e[i]){
            if(y == fa[i])continue;
            if(siz[y] < s)res += siz[y];
        }
        if(res != s)return false;
    }

    for(int i = n + 1;i <= n + cnt; ++i){
        if(siz[i] < s)continue;
        for(auto y : e[i]){
            if(y == fa[i])continue;
            if(siz[y] < s)return false;
        }
    }

    return Ciallo;
}


int main(int argc, char* argv[]){
    freopen("cities.in", "r", stdin);
    freopen("cities.out", "w", stdout);
    #ifdef FS
        freopen(argv[1], "r", stdin);
        freopen(argv[2], "w", stdout);
    #elif defined(LOCAL)
        freopen("w.in", "r", stdin);
        freopen("w.out", "w", stdout);
    #endif

    n = read(),m = read(),k = read();
    if(k == 1){
        cout << "I can't do it\n";
        return 0;
    }

    for(int i = 1;i <= m; ++i){
        int x = read(),y = read();
        add(x, y);
        add(y, x);
    }

    Tarjan(1, 0);
    rot = 0, mu = 1e9;
    getrot(1, 0);
    getsiz(rot, 0);
    // cerr << rot << endl;
    // for(int i = 1;i <= n + idx; ++i)cerr << siz[i] << " ";
    // cerr << endl;

    int ans = 0;
    for(int i = 1;i < n; ++i){
        if(n % i == 0){
            if(chk0(i)){
                ++ ans;
                // cerr << i << endl;
            }
        }
    }
    cout << ans << endl;

    cerr << "Time : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";
    return 0;
}