#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

int main(){
	int n,m; scanf("%d%d",&n,&m);
	static int U[200000],V[200000],deg[100000];
	rep(i,m){
		scanf("%d%d",U+i,V+i), U[i]--, V[i]--;
		int u=U[i],v=V[i];
		deg[u]++;
		deg[v]++;
	}

	static bool del[100000]; // 選ばない頂点
	static int sz[100000]; // sz[u] := ( 頂点 u と平等な ( u の代わりに選んでもいい ) 頂点の個数 )
	rep(u,n) sz[u]=1;
	rep(i,m){
		int u=U[i],v=V[i];
		if(deg[u]<deg[v] || deg[u]==deg[v] && u<v) del[v]=true;
		else                                       del[u]=true;

		if(deg[u]==deg[v]) sz[u]++, sz[v]++;
	}

	int ans1=0;
	ll ans2=1;
	rep(u,n) if(!del[u]) {
		ans1++;
		ans2=ans2*sz[u]%1000000009;
	}
	printf("%d\n%lld\n",ans1,ans2);

	return 0;
}