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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000009;
typedef pair<vint,vpint>graph;
pint op(const pint &a,const pint &b){
    return {a.fi+b.fi,a.se*b.se%mod};
}

vint G[100000];
int deg[100000];
int mark[100000];
int sizev[100000];
int sizee[200000];
pint ans;
int que[100000],tail;

int vs_[100000];pint es_[200000];

void solve2(int N,int *vs,int M,pint *es);

void solve(int N,int *vs,int M,pint *es){
    rep(i,N)deg[vs[i]]=0,mark[vs[i]]=-1;

    for(int i=0;i<M;i++){
        G[es[i].fi][deg[es[i].fi]++]=es[i].se;
        G[es[i].se][deg[es[i].se]++]=es[i].fi;
    }

    vector<int>sizev,sizee;

    int cnt=0;
    for(int i=0;i<N;i++){
        if(mark[vs[i]]!=-1)continue;
        sizev.pb(0);sizee.pb(0);
        int c=cnt++;
        sizev[c]++;
        mark[vs[i]]=c;
        tail=1;
        que[0]=vs[i];
        for(int j=0;j<tail;j++){
            int v=que[j];
            for(int k=0;k<deg[v];k++){
                int u=G[v][k];
                if(mark[u]!=-1)continue;
                mark[u]=c;
                sizev[c]++;
                que[tail++]=u;
            }
        }
    }

    for(int i=0;i<M;i++)sizee[mark[es[i].fi]]++;
    rep(i,N)vs_[i]=vs[i];
    rep(i,M)es_[i]=es[i];

    int c=0;
    for(int i=0;i<cnt;i++){
        int nc=sizev[i]+c;
        sizev[i]=c;
        c=nc;
    }

    c=0;
    for(int i=0;i<cnt;i++){
        int nc=sizee[i]+c;
        sizee[i]=c;
        c=nc;
    }

    rep(i,N){
        int tmp=sizev[mark[vs_[i]]]++;
        vs[tmp]=vs_[i];
    }

    rep(i,M){
        int tmp=sizee[mark[es_[i].fi]]++;
        es[tmp]=es_[i];
    }

    rep(i,cnt){
        int t=i?sizev[i-1]:0;
        int s=i?sizee[i-1]:0;
        solve2(sizev[i]-t,vs+t,sizee[i]-s,es+s);
    }
}

void solve2(int N,int *vs,int M,pint *es){
    if(N*(N-1)/2==M){
        ans=op(ans,{1,N});
        return;
    }

    rep(i,N)deg[vs[i]]=0;

    for(int i=0;i<M;i++)deg[es[i].fi]++,deg[es[i].se]++;
    int cent=-1;
    rep(i,N){
        if(deg[vs[i]]==N-1)cent=vs[i];
        deg[vs[i]]=0;
    }
    assert(cent!=-1);

    int t=0;
    rep(i,N){
        if(vs[i]==cent)continue;
        vs[t++]=vs[i];
    }

    int s=0;
    rep(i,M){
        if(es[i].fi==cent||es[i].se==cent)continue;
        es[s++]=es[i];
    }
    solve(t,vs,s,es);
}

signed main(){
    int N,M;
    scanf("%lld%lld",&N,&M);


    static int vs[100000];
    static pint es[200000];
    rep(i,N)vs[i]=i;
    rep(i,M){
        int a,b;
        scanf("%lld%lld",&a,&b);
        a--;b--;
        es[i]={a,b};
        G[a].pb(b);G[b].pb(a);
    }

    memset(mark,-1,sizeof(mark));
    ans={0,1};
    solve(N,vs,M,es);
    printf("%lld\n%lld\n",ans.fi,ans.se);
    return 0;
}

Measured memory_bytes: 21960