#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(__typeof__(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}



const int MOD = 1000000009;
const int MAX_V = 100100;
struct Graph {
    int V;
    vector<int> list[MAX_V];
    
    Graph(int n = 0) : V(n) {}
    void init(int n = 0) {V = n; for (int i = 0; i < MAX_V; ++i) list[i].clear();}
    inline vector<int>& operator [] (int i) {return list[i];}
    
    void connect(int f, int t) {
        list[f].push_back(t);
        list[t].push_back(f);
    }
} G;  


vector<vint> rem;

int N, M, x, y;
bool dame[MAX_V];
vint temp;
vector<vint> comp;


bool seen[MAX_V];
void dfs(int v) {
    seen[v] = true;
    for (int i = 0; i < rem[v].size(); ++i) {
        int next = rem[v][i];
        if (!seen[next]) dfs(next);
    }
    temp.PB(v);
}

int main() {
    memset(dame, 0, sizeof(dame));
    scanf("%d %d", &N, &M);
    G.init(N);
    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &x, &y);
        --x; --y;
        G.connect(x, y);
    }
    
    for (int i = 0; i < N; ++i) {
        if (dame[i]) continue;

        for (int j = 0; j < G[i].size(); ++j) {
            int to = G[i][j];
            if (G[to].size() < G[i].size()) {
                dame[i] = true;
            }
            else if (G[to].size() > G[i].size()) {
                dame[to] = true;
            }
        }
    }
    
    rem.clear();
    rem.resize(N, vint());
    for (int i = 0; i < N; ++i) {
        if (dame[i]) continue;
        for (int j = 0; j < G[i].size(); ++j) {
            if (!dame[G[i][j]]) {
                rem[i].PB(G[i][j]);
            }
        }
    }
    
    //COUT(rem);
    
    memset(seen, 0, sizeof(seen));
    for (int i = 0; i < N; ++i) {
        if (!seen[i] && !dame[i]) {
            temp.clear();
            dfs(i);
            comp.PB(temp);
        }
    }
    
    //COUT(comp);
    
    int con = comp.size();
    ll res = 1;
    for (int i = 0; i < con; ++i) {
        res *= comp[i].size();
        res %= MOD;
    }
    
    cout << con << endl;
    cout << res << endl;
    
    return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to train your eyesight and concentration by observing many stars shining in the night sky. Rabbits can record the characteristics of stars with their own sense.

Rabbit decided to add the characteristics of the stars recorded as "Star Observation Diary" to his notebook. Here, we want to avoid recording two "similar" stars together. Whether or not the two stars are "similar" is all determined by the rabbit's judgment. The relationship of "similarity" is not so complicated and satisfies the following conditions.

> Condition: There are four different stars A, B, C, D, and A and B, B and C, and C and D are "similar" respectively. At this time, A and C are "similar", B and D are "similar", or both.

Rabbits want to record as many stars as possible without recording two "similar" stars. I also want to know how many ways to do that.



Input


N M
X1 Y1
...
XM YM


N is the number of stars and M is the number of pairs of two "similar" stars. A star is represented by an integer number greater than or equal to 1 and less than or equal to N, and Xi, Yi (1 ≤ i ≤ M) indicates that the star Xi and the star Yi are "similar".

Satisfy 1 ≤ N ≤ 100,000, 0 ≤ M ≤ 200,000, 1 ≤ Xi <Yi ≤ N. The same set as (Xi, Yi) does not appear multiple times. The relationship of "similarity" satisfies the condition specified in the problem statement.

Output

The first line shows the maximum number of stars that can be recorded so that two "similar" stars are not recorded, and the second line shows the number of star combinations that can achieve that maximum (only the order in which they are recorded). Divide the changed one by 1,000,000,009 and output the remainder.

Examples

Input

4 3
1 2
1 3
1 4


Output

3
1


Input

11 5
1 2
3 4
5 6
7 8
9 10


Output

6
32


Input

9 14
1 2
1 3
2 3
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
5 6
7 8
8 9


Output

4
6

### Response

```cpp
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;

#define DE 1
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
#define ALL(s) (s).begin(),(s).end()
#define REP(i,n) for (int i = 0; i < (int)(n); ++i)
#define EACH(i,s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl

template<class T1, class T2> ostream& operator<<(ostream &s, pair<T1,T2> P){return s<<'<'<<P.first<<", "<<P.second<<'>';}
template<class T> ostream& operator<<(ostream &s, vector<T> P) {s<<"{ ";for(int i=0;i<P.size();++i){if(i>0)s<<", ";s<<P[i];}return s<<" }"<<endl;}
template<class T1, class T2> ostream& operator<<(ostream &s, map<T1,T2> P) {s<<"{ ";for(__typeof__(P.begin()) it=P.begin();it!=P.end();++it){if(it!=P.begin())s<<", ";s<<'<'<<it->first<<"->"<<it->second<<'>';}return s<<" }"<<endl;}



const int MOD = 1000000009;
const int MAX_V = 100100;
struct Graph {
    int V;
    vector<int> list[MAX_V];
    
    Graph(int n = 0) : V(n) {}
    void init(int n = 0) {V = n; for (int i = 0; i < MAX_V; ++i) list[i].clear();}
    inline vector<int>& operator [] (int i) {return list[i];}
    
    void connect(int f, int t) {
        list[f].push_back(t);
        list[t].push_back(f);
    }
} G;  


vector<vint> rem;

int N, M, x, y;
bool dame[MAX_V];
vint temp;
vector<vint> comp;


bool seen[MAX_V];
void dfs(int v) {
    seen[v] = true;
    for (int i = 0; i < rem[v].size(); ++i) {
        int next = rem[v][i];
        if (!seen[next]) dfs(next);
    }
    temp.PB(v);
}

int main() {
    memset(dame, 0, sizeof(dame));
    scanf("%d %d", &N, &M);
    G.init(N);
    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &x, &y);
        --x; --y;
        G.connect(x, y);
    }
    
    for (int i = 0; i < N; ++i) {
        if (dame[i]) continue;

        for (int j = 0; j < G[i].size(); ++j) {
            int to = G[i][j];
            if (G[to].size() < G[i].size()) {
                dame[i] = true;
            }
            else if (G[to].size() > G[i].size()) {
                dame[to] = true;
            }
        }
    }
    
    rem.clear();
    rem.resize(N, vint());
    for (int i = 0; i < N; ++i) {
        if (dame[i]) continue;
        for (int j = 0; j < G[i].size(); ++j) {
            if (!dame[G[i][j]]) {
                rem[i].PB(G[i][j]);
            }
        }
    }
    
    //COUT(rem);
    
    memset(seen, 0, sizeof(seen));
    for (int i = 0; i < N; ++i) {
        if (!seen[i] && !dame[i]) {
            temp.clear();
            dfs(i);
            comp.PB(temp);
        }
    }
    
    //COUT(comp);
    
    int con = comp.size();
    ll res = 1;
    for (int i = 0; i < con; ++i) {
        res *= comp[i].size();
        res %= MOD;
    }
    
    cout << con << endl;
    cout << res << endl;
    
    return 0;
}

```