Submission #3423264

---

Source Code Expand

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);++i)
#define rrep(i,n) for(int (i)=(n)-1;(i)>=0;--i)
#define rep1(i,n) for(int (i)=1;(i)<=(n);++i)
#define rrep1(i,n) for(int (i)=(n);(i)>=1;--i)
#define pb push_back
#define fr first
#define sc second
typedef long long ll;
typedef pair<int,int> P;
typedef pair<long long,long long> LP;
typedef double db;
using namespace std;

ll N,M;
ll A[100000],B[100000];
int X[100000];
vector<ll> vs[100000];
ll C[2];

bool dfs(int v,int p,int val){
  if(X[v] == -1){
    X[v]=val;
    C[val]++;
    rep(i,vs[v].size()){
      if(p == vs[v][i]) continue;
      if( dfs(vs[v][i], v, !val ) ) return 1;
    }
  }
  else if(X[v] != val){
    return 1;
  }
  return 0;
}

int main()
{
  cin>>N>>M;
  rep(i,M){
    cin>>A[i]>>B[i];
    A[i]--;
    B[i]--;
    vs[A[i]].pb(B[i]);
    vs[B[i]].pb(A[i]);
  }
  memset(X,-1,sizeof(X));
  if(dfs(0,-1,0)){
    cout << (N*(N-1)/2)-M<<endl;
  }
  else{
    cout<< C[0]*C[1]-M<<endl;
  }
}

Submission Info

Judge Result