小清新分类讨论题
首先不难发现这题加边的上界就是\(3\)，并且只有当图中一条边没有时才会取得，方案数就是\(C_n^3\)
而一条边不加的情况也很容易，可以先跑个染色看下有没有奇环，如果有的话就直接输出即可
而加两条边的情况也比较简单，当图中都是孤立边和孤立点时（即所有点度数均\(\le 1\)），则需要加两条边，方案数为\(m\times (n-2)\)
而加一条边的情况就稍微麻烦一点，我们要用加入的这条边来连接两个已经连通且之间距离为偶数的点
不难发现这对应的就是统一连通块内的同色点，因此设某连通块内黑/白点数量为\(c_0/c_1\)，则该连通块对方案数的贡献为\(C_{c_0}^2+C_{c_1}^2\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,m,x,y,col[N],odd_cycle,c[2]; vector <int> v[N]; LL ans;
inline void DFS(CI now)
{
if (odd_cycle) return; ++c[col[now]];
for (auto to:v[now]) if (!~col[to]) col[to]=col[now]^1,DFS(to);
else if (col[to]!=(col[now]^1)) return (void)(odd_cycle=1);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
if (m==0) return printf("3 %lld",1LL*n*(n-1)*(n-2)/6LL),0;
auto C2=[&](CI x)
{
return 1LL*x*(x-1)/2LL;
};
for (memset(col,-1,sizeof(col)),i=1;i<=n;++i) if (!~col[i])
col[i]=c[0]=c[1]=0,DFS(i),ans+=C2(c[0])+C2(c[1]);
if (odd_cycle) return puts("0 1"),0;
bool small_deg=1; for (i=1;i<=n;++i) if (v[i].size()>=2) { small_deg=0; break; }
if (small_deg) return printf("2 %lld",1LL*m*(n-2)),0;
return printf("1 %lld",ans),0;
}