飞机票：http://codeforces.com/contest/557/problem/D

题意：给你n个点和m条边的无向图，可能不是连接在一起的，并且没有子环和平行边，求最小添加几条边可以使它包含奇数点的圈，并且求满足这样方案的方法有多少种，两种方案不同即边的设置不完全一样。

分析：起先可以很容易知道最少的边不会超过3，即0，1，2，3，为什么？加入所有的点都不相连，即m等于0，那么肯定对任意三点添加三条边就可以有奇数点的圈，总方案就是C（n,3）即n*(n-1)*(n-2)/3;然后就可以用染色的方法对0，1，2进行判断，具体怎么判断，假设当前点为i，且i没有访问过，那么对i进行DFS，可以设i点的颜色为0，与i相连的点颜色为1，并且对i相连的没有访问过的边继续按照这个染色方法染色，即当前点的颜色为0，则相连的边为1，反之同理。假设当前的节点为now,它的邻边v被访问过，如果它们的颜色一样的话，就说明包含奇数点的圈，为什么？因为点是根据0，1，0，1染色的，因为两个相邻的颜色一样，说明，就是1，0，1，0，....1，因为没有最后一个点，它就是偶数个，包含了，它就是奇数个，只要是这样，就说明不用添加边，则为0条边，一种方法。反之的话，继续搜索，并且记录，染色为1的点的个数，和染色为0的点的个数。当搜索完的时候，得到为1的点为p,为0的点的数量为q,我们要使它包含奇数个点，所以我们要选择两个点，且它们之间的数量为奇数，因为我们知道只要两个点的颜色一样，则它们之间肯定包含了奇数个点的圈，所以我们从p里选择两个，即C（p,2）=p*(p-)/2，同理从q中选两个C(q,2)=q*(q-)/2，加到总方法里去，对每一块都分别进行统计，当计算完的时候，当总数为0的时候，又因为m不等于0，所以最多是2个点相连，所以总数就是m*(n-2)，即m里选择条边，n-2选择一个点，然后输出，这时候我们必须添加两条边，如果总数大于0，则最多只要添加一条边，输出答案就好，最后啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=123456;
vector<int> V[maxn];
int n,m;
void init()
{
    for(int i=1; i<=n; i++)V[i].clear();
    int u,v;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        V[u].push_back(v);
        V[v].push_back(u);
    }
}
bool vis[maxn];
bool color[maxn];
LL cc[2];
bool flag;
LL MIN;
void DFS(int now)
{
    vis[now]=1;
    cc[color[now]]++;
    for(int i=0; i<V[now].size(); i++)
    {
        int v=V[now][i];
        if(!vis[v])
        {
            color[v]=!color[now];
            DFS(v);
        }
        else if(color[v]==color[now])
        {
            flag=1;
        }
    }
}
void play()
{
    if(m==0){
        LL ans=1LL*n*(n-1)*(n-2)/6;
        printf("3 %I64d\n",ans);
        return;
    }
    memset(vis,0,sizeof(vis));
    flag=0;
    LL ans=0;
    memset(color,0,sizeof(color));
    for(int i=1; i<=n; i++)
    {
        if(vis[i])continue;
        cc[0]=cc[1]=0;
        DFS(i);
        if(flag){
            printf("0 1\n");
            return;
        }
        ans+=cc[0]*(cc[0]-1)/2;
        ans+=cc[1]*(cc[1]-1)/2;
    }
    if(ans==0){
        printf("2 %I64d\n",1LL*m*(n-2));
        return;
    }
    printf("1 %I64d\n",ans);


}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}