stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include        <map>

#include      <cmath>

#include      <queue>

#include     <string>

#include     <cstdio>

#include     <vector>

#include    <cstring>

#include   <iostream>

#include  <algorithm>

using namespace std;

#define ll long long

const ll inf = 0x3f3f3f3f;

const int maxn = 1e5+5;

const ll mod = 1e9+7;



int a[maxn];

int b[maxn];



int main(){

    int n;

    scanf("%d",&n);

    for(int i=0;i<=n;i++){

        scanf("%d",&a[i]);

    }

    for(int i=0;i<n;i++){

        scanf("%d",&b[i]);

    }

    ll ans = 0;

    for(int i=0;i<n;i++){

        if(b[i]>a[i]){

            ans += a[i];

            b[i] -= a[i];

            if(b[i]>a[i+1]){

                ans += a[i+1];

                a[i+1] = 0;

                b[i] -= a[i+1];

            }else {

                ans += b[i];

                a[i+1] -= b[i];

                b[i] = 0;

            }

        }else {

            ans += b[i];

        }

    }

    printf("%lld\n",ans);

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll cun[1000000];

ll hero[1000000];

int main()

{

	int n;

	ll sum=0;

	scanf("%d",&n);

	for(int i=0;i<n+1;i++)

	{

		scanf("%lld",&cun[i]);

	}

	for(int i=0;i<n;i++)

	{

		scanf("%lld",&hero[i]);

	}

	

	for(int i=0;i<n;i++)

	{

		if(hero[i]>cun[i])

		{

			sum+=cun[i];

			hero[i]-=cun[i];

			cun[i]=0;

			//printf("heroi1=%d\n",hero[i]);

			

			if(cun[i+1]>hero[i])

			{

				sum+=hero[i];

			//	printf("heroi2=%d\n",hero[i]);

				cun[i+1]-=hero[i];

				hero[i]=0;

			}

			else

			{

				sum+=cun[i+1];

				hero[i]-=cun[i+1];

				cun[i+1]=0;

			}

		}

		else

		{

			sum+=hero[i];

			cun[i]-=hero[i];

		}

	//	printf("test%d %d\n",sum,hero[i]);

	}

	printf("%lld",sum);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <vector>

#include <iostream>

#include <cmath>

#define INF 500000+500

#define Max 0x3f3f3f3f

#define Mod 1000000007

typedef long long int ll;

using namespace std;

ll arr[INF],brr[INF];

ll sum1[INF];

int main() 

{

	ll n;

	cin >> n;

	ll t = n+1;

	for(int i=1; i<=t; i++) {

		cin >> arr[i];

	}

	ll cnt=0;

	for(int i=1; i<=n; i++) {

		cin >> brr[i];

		if(brr[i]<=arr[i])	cnt+=brr[i];

		else if(brr[i]<=arr[i]+arr[i+1]) {

			cnt += brr[i];

			arr[i+1] -= brr[i]-arr[i];

		}else{

			cnt += arr[i]+arr[i+1];

			arr[i+1] = 0;

		}

	}

	cout << cnt << endl;

	

	

	

	

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll cun[1000000];

ll hero[1000000];

int main()

{

	int n;

	ll sum=0;

	scanf("%d",&n);

	for(int i=0;i<n+1;i++)

	{

		scanf("%lld",&cun[i]);

	}

	for(int i=0;i<n;i++)

	{

		scanf("%lld",&hero[i]);

	}

	

	for(int i=0;i<n;i++)

	{

		if(hero[i]>cun[i])

		{

			sum+=cun[i];

			hero[i]-=cun[i];

			cun[i]=0;

			//printf("heroi1=%d\n",hero[i]);

			

			if(cun[i+1]>hero[i])

			{

				sum+=hero[i];

			//	printf("heroi2=%d\n",hero[i]);

				cun[i+1]-=hero[i];

				hero[i]=0;

			}

			else

			{

				sum+=cun[i+1];

				hero[i]-=cun[i+1];

				cun[i+1]=0;

			}

		}

		else

		{

			sum+=hero[i];

			cun[i]-=hero[i];

		}

	//	printf("test%d %d\n",sum,hero[i]);

	}

	printf("%lld",sum);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#include<algorithm>

using namespace std;

int a[100002][2];

int main()

{



    int i,j,n,m;

    cin>>n;

    for(i=0; i<n+1; i++)

        cin>>a[i][0];

    for(i=0; i<n; i++)

        cin>>a[i][1];

    long long int sum=0;

    for(i=0; i<n; i++)

    {

        if(a[i][1]<=a[i][0])

            sum+=a[i][1];

        else

        {

            a[i][1]-=a[i][0];

            sum+=a[i][0];

            if(a[i+1][0]>=a[i][1])

            {

                a[i+1][0]-=a[i][1];

                sum+=a[i][1];

            }

            else

            {

                sum+=a[i+1][0];

                a[i+1][0]=0;

            }

        }

    }

    cout<<sum;

    }


// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long int ll;



const int MAXN = 1e5 + 5;



int n;

ll ans;

ll A[MAXN], B[MAXN];



int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n + 1; ++i) {

        scanf("%lld", &A[i]);

    }

    for (int i = 1; i <= n; ++i) {

        scanf("%lld", &B[i]);

        if (B[i] <= A[i])

            ans += B[i];

        else if (B[i] <= A[i] + A[i + 1]) {

            ans += B[i];

            A[i + 1] -= (B[i] - A[i]);

        }

        else {

            ans += (A[i] + A[i + 1]);

            A[i + 1] = 0;

        }

    }

    printf("%lld", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream> 

using namespace std;

#include <cstdio>

#include <string>

#include <vector>

#include <queue>

#include <algorithm>

const int N = 1e5+10;

typedef long long ll;

ll a[N];

ll b[N];



int main()

{

	ll n;

	cin >> n;

	

	ll sum = 0;

	

	for (ll i = 0; i < n+1 ; i ++ ) cin >> a[i];

	

	for (ll i = 0; i < n; i ++ ) cin >> b[i];

	

	for (ll i = 0; i < n; i ++ )

	{

		if(a[i] < b[i])

		{

			sum += a[i];

			ll t = b[i] - a[i];

			if(t >= a[i+1])

			{

				sum += a[i+1];

				a[i+1] = 0;

			}

			else

			{

				sum += t;

				a[i+1] -= t;

			}

		}

		else

		{

			a[i] -= b[i];

			sum += b[i];

		}

	}

	

	cout << sum << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long int ll;



const int MAXN = 1e5 + 5;



int n;

ll ans;

ll A[MAXN], B[MAXN];



int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n + 1; ++i) {

        scanf("%lld", &A[i]);

    }

    for (int i = 1; i <= n; ++i) {

        scanf("%lld", &B[i]);

        if (B[i] <= A[i])

            ans += B[i];

        else if (B[i] <= A[i] + A[i + 1]) {

            ans += B[i];

            A[i + 1] -= (B[i] - A[i]);

        }

        else {

            ans += (A[i] + A[i + 1]);

            A[i + 1] = 0;

        }

    }

    printf("%lld", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include<bits/stdc++.h>



using namespace std;



typedef long long int ll;

const int MAXN = 100005;



int n;

ll ans;

ll a[MAXN], B[MAXN];



int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n + 1; ++i) 

	{

        scanf("%lld", &a[i]);

    }

    for (int i = 1; i < n + 1; ++i)

	{

        scanf("%lld", &B[i]);

        if (B[i] <= a[i])

            ans += B[i];

        else if (B[i] <= a[i] + a[i + 1]) 

		{

            ans += B[i];

            a[i + 1] -= (B[i] - a[i]);

        }

        else 

		{

            ans += (a[i] + a[i + 1]);

            a[i + 1] = 0;

        }

    }

    printf("%lld\n", ans);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long int ll;



const int MAXN = 1e5 + 5;



int n;

ll ans;

ll A[MAXN], B[MAXN];



int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n + 1; ++i) {

        scanf("%lld", &A[i]);

    }

    for (int i = 1; i <= n; ++i) {

        scanf("%lld", &B[i]);

        if (B[i] <= A[i])

            ans += B[i];

        else if (B[i] <= A[i] + A[i + 1]) {

            ans += B[i];

            A[i + 1] -= (B[i] - A[i]);

        }

        else {

            ans += (A[i] + A[i + 1]);

            A[i + 1] = 0;

        }

    }

    printf("%lld", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*zxj*/

#include<iostream> 

#include<string>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<sstream>

#define sf scanf

#define pf printf

#define pfn printf("\n");

#define pfk printf(" ");

#define pf0 printf("0");

#define pf1 printf("1");

#define ll long long

#define sfd(n) scanf("%d",&n);

#define sfdd(n,m) scanf("%d%d",&n,&m);

#define sfld(n) scanf("%lld",&n);

#define sfldd(n,m) scanf("%lld%lld",&n,&m);

#define sflf(n) scanf("%lf",&n);

#define sflff(n,m) scanf("%lf%lf",&n,&m);

#define sfc(n) scanf("%c",n);

#define sfcc(n,m) scanf("%c%c",n,m);

#define sfs(n) scanf("%s",n);

#define sfss(n,m) scanf("%s%s",n,m);

#define pfd(n) printf("%d",n);

#define pfld(n) printf("%lld",n);

#define pflf(n) printf("%lf",n);

#define pfc(n) printf("%c",n);

#define pfs(n) printf("%s",n);

using namespace std;

#define csh(a,n) memset(a,n,sizeof(a));

ll arr[1000000];

int main(){

	ll sum=0;

	ll n;

	cin>>n;

	for(ll i=0;i<n+1;i++){

		cin>>arr[i];

	}

	for(ll i=0;i<n;i++){

		ll a;

		cin>>a;

		if(a>arr[i]){

			a-=arr[i];

			sum+=arr[i];

			if(a>arr[i+1]){

				sum+=arr[i+1]; 

				arr[i+1]=0;

			}

			else{

				arr[i+1]-=a;

				sum+=a;

			}

		}

		else{

			sum+=a;

		}

	}

	cout<<sum<<endl;

}

// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long int ll;



const int MAXN = 1e5 + 5;



int n;

ll ans;

ll A[MAXN], B[MAXN];



int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n + 1; ++i) {

        scanf("%lld", &A[i]);

    }

    for (int i = 1; i <= n; ++i) {

        scanf("%lld", &B[i]);

        if (B[i] <= A[i])

            ans += B[i];

        else if (B[i] <= A[i] + A[i + 1]) {

            ans += B[i];

            A[i + 1] -= (B[i] - A[i]);

        }

        else {

            ans += (A[i] + A[i + 1]);

            A[i + 1] = 0;

        }

    }

    printf("%lld", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<algorithm>

#include<string.h>

using namespace std;

#define ll long long 

int main()

{

	ll n;

	cin>>n;

	ll a[111111];

	for(int i=0;i<n+1;i++)

	{

		cin>>a[i];

	}

	ll sum=0;

	ll b;

	for(int i=0;i<n;i++)

	{

		cin>>b;

		if(b>=a[i])

		{

			sum+=a[i];

			b-=a[i];

			if(b>=a[i+1])

			{

				sum+=a[i+1];

				a[i+1]=0;

			}

			else

			{

				sum+=b;

				a[i+1]-=b;

			}

		}

		else

		{

			sum+=b;

		}

	}

	cout<<sum<<endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>



typedef long long int ll;



const int MAXN = 1e5 + 5;



int n;

ll ans;

ll A[MAXN], B[MAXN];



int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n + 1; ++i) {

        scanf("%lld", &A[i]);

    }

    for (int i = 1; i <= n; ++i) {

        scanf("%lld", &B[i]);

        if (B[i] <= A[i])

            ans += B[i];

        else if (B[i] <= A[i] + A[i + 1]) {

            ans += B[i];

            A[i + 1] -= (B[i] - A[i]);

        }

        else {

            ans += (A[i] + A[i + 1]);

            A[i + 1] = 0;

        }

    }

    printf("%lld", ans);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <string.h>

using namespace std;



#define pb push_back

#define int long long

const int N = 1e5+5;

int n, m, u, v;

int color[N];

bool visited[N], congthu = 1;

vector<int> adj[N];



void dfs(int u, int c)

{

    for (auto v: adj[u])

    {

        if(color[v] != -1 && color[v] != c) {

            congthu = 0;

        }

        color[v] = c;

    }

    for (auto v: adj[u])

    {

        if(!visited[v]) {

            visited[v] = 1;

            dfs(v, 1 - c);

        }

    }

}



signed main()

{

    cin >> n >> m;

    for (int i = 0; i < m; i++)

    {

        cin >> u >> v;

        adj[u].pb(v);

        adj[v].pb(u);

    }

    memset(color, -1, sizeof color);

    color[1] = 1;

    visited[1] = 1;

    dfs(1, 0);

    if (!congthu)

        cout << n*(n-1)/2 - m;

    else

    {

        int black = 0, white = 0;

        for (int i = 1; i <= n; i++)

        {

            if (color[i] == 1) black++;

            else if (color[i] == 0) white++;

        }

        cout << black*white-m;

    }

}

/*

6 5

1 2

2 3

3 4

4 5

5 6

*/


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



const int N = 110000;



vector<int> con[N];

int vis[N];



bool dfs(int u, int col) {

	vis[u] = col;

	for (int v : con[u]) {

		if (vis[v] && 3 - col != vis[v]) return false;

		if (!vis[v] && !dfs(v, 3 - col)) return false;

	}

	return true;

}



int main() {

	

	ios::sync_with_stdio(0);

	cin.tie(0), cout.tie(0);

	

	int n, m; cin >> n >> m;

	for (int i = 0; i < m; i++) {

		int u, v; cin >> u >> v;

		con[u].push_back(v), con[v].push_back(u);

	}

	

	if (!dfs(1, 1)) cout << (long long)n * (n - 1) / 2 - m << "\n";

	else {

		int cnt = 0;

		for (int i = 1; i <= n; i++) cnt += vis[i] == 1;

		cout << (long long)cnt * (n - cnt) - m << "\n";

	}

	

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#pragma GCC optimize(3)

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<list>

#include<queue>

#include<stack>

#include<bitset>

#include<deque>

using namespace std;

#define ll long long

// #define inf 0x3f3f3f3f

#define ri register int

#define il inline

#define fi first

#define se second

#define mp make_pair

#define pi pair<int,int>

#define mem0(x) memset((x),0,sizeof (x))

#define mem1(x) memset((x),0x3f,sizeof (x))

il char gc()

{

    static const int BS = 1 << 22;

    static unsigned char buf[BS], *st, *ed;

    if (st == ed) ed = buf + fread(st = buf, 1, BS, stdin);

    return st == ed ? EOF : *st++;

}

#define gc getchar

template<class T>void in(T &x)

{

    x = 0;

    bool f = 0;

    char c = gc();

    while (c < '0' || c > '9')

    {

        if (c == '-') f = 1;

        c = gc();

    }

    while ('0' <= c && c <= '9')

    {

        x = (x << 3) + (x << 1) + (c ^ 48);

        c = gc();

    }

    if (f) x = -x;

}

#undef gc

#define pb push_back

#define N 100010

#define M N<<1

int n, m;

int v[M], nx[M];

int cnt, head[N];

il void add(int uu, int vv)

{

    v[++cnt] = vv, nx[cnt] = head[uu];

    head[uu] = cnt;

}

int col[N];

bool ok = 1;

int sz;

void dfs(int x)

{

    if (col[x] == 2) ++sz;

    for (ri i = head[x]; i; i = nx[i])

    {

        if (col[v[i]])

        {

            if (col[v[i]] == col[x])

            {

                ok = 0;

                return;

            }

        }

        else

        {

            col[v[i]] = col[x] ^ 1;

            dfs(v[i]);

        }

    }

}

signed main()

{

#ifndef ONLINE_JUDGE

    //freopen("in.in", "r", stdin);

#endif

    in(n), in(m);

    for (ri i = 1, a, b; i <= m; ++i)

    {

        in(a), in(b);

        add(a, b);

        add(b, a);

    }

    col[1] = 2;

    dfs(1);

    if (ok == 0)

    {

        printf("%lld", (ll)n * (n - 1) / 2 - m);

    }

    else

    {

        printf("%lld", (ll)sz * (n - sz) - m);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>//T2

#define For(i,a,b) for(register long long i=a;i<=b;i++)

#define Rof(i,a,b) for(register long long i=a;i>=b;i--)

#define int long long

using namespace std;

const int maxn=1e5+10;

int fa[maxn<<1];

inline int findfa(int i){

	return i==fa[i]?i:fa[i]=findfa(fa[i]);

}

inline void uni(int i,int j){

	int a=findfa(i),b=findfa(j);

	if(a!=b) fa[a]=b;

}

inline bool wxp(int i,int j){

	return findfa(i)==findfa(j);

}

int n,m;

signed main(){

	scanf("%lld%lld",&n,&m);

	Rof(i,n<<1,1){

		fa[i]=i;

	}

	For(i,1,m){

		int u,v;

		scanf("%lld%lld",&u,&v);

		uni(u,v+n);

		uni(u+n,v);

	}

	For(i,1,n){

		if(wxp(i,i+n)){

			printf("%lld\n",n*(n-1)/2-m);

			return 0;

		}

	}

	int ls=1,rs=0;

	For(i,2,n){

		if(wxp(i,1)){

			++ls;

		}else{

			++rs;

		}

	}

	printf("%lld\n",ls*rs-m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;



namespace io {

#define gc() (iS == iT ? (iT = (iS = ibuff) + fread(ibuff, 1, SIZ, stdin), (iS == iT ? EOF : *iS++)) : *iS++)

	const int SIZ = 1 << 21 | 1;

	char *iS, *iT, ibuff[SIZ], obuff[SIZ], *oS = obuff, *oT = oS + SIZ - 1, fu[110], c;

	int fr;

	inline void out() {

		fwrite(obuff, 1, oS - obuff, stdout);

		oS = obuff;

	}

	template<class Type>

	inline void read(Type &x) {

		x = 0;

		Type y = 1;

		for (c = gc(); (c > '9' || c < '0') && c != '-'; c = gc());

		c == '-' ? y = -1 : x = (c & 15);

		for (c = gc(); c >= '0' && c <= '9'; c = gc())

			x = x * 10 + (c & 15);

		x *= y;

	}

	template<class Type>

	inline void print(Type x, char text = '\n') {

		if (x < 0)

			*oS++ = '-', x *= -1;

		if (x == 0)

			*oS++ = '0';

		while (x)

			fu[++fr] = x % 10 + '0', x /= 10;

		while (fr)

			*oS++ = fu[fr--];

		*oS++ = text;

		out();

	}

}

using namespace io;

#define ll long long

const int maxn = 100010;



int n, m, a, b;

int col[maxn + 5], lnk[maxn + 5], son[maxn << 1], nxt[maxn << 1];

int u;



inline void Add(int x, int y) {

	son[++u] = y;

	nxt[u] = lnk[x];

	lnk[x] = u;

}



void dfs(int x, int now = 0, int fa = 0) {

	col[x] = now; now ^= 1;

	for (int j = lnk[x]; j; j = nxt[j]) {

		if (col[son[j]] == -1)

			dfs(son[j], now, x);

		if (col[son[j]] != now)

			print((ll)n*(n - 1) / 2 - m), exit(0);

	}

}



int main() {

	read(n);

	read(m);

	memset(col, 255, sizeof(col));

	for (int i = 1, x, y; i <= m; i++)

		read(x), read(y), Add(x, y), Add(y, x);

	dfs(1);

	for (int i = 1; i <= n; i++)

		col[i] ? ++a : ++b;

	print((ll)a * b - m);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>//T2

#define For(i,a,b) for(register long long i=a;i<=b;i++)

#define Rof(i,a,b) for(register long long i=a;i>=b;i--)

#define int long long

using namespace std;

const int maxn=1e5+10;

int fa[maxn<<1];

inline int findfa(int i){

	return i==fa[i]?i:fa[i]=findfa(fa[i]);

}

inline void uni(int i,int j){

	int a=findfa(i),b=findfa(j);

	if(a!=b) fa[a]=b;

}

inline bool wxp(int i,int j){

	return findfa(i)==findfa(j);

}

int n,m;

signed main(){

	scanf("%lld%lld",&n,&m);

	Rof(i,n<<1,1){

		fa[i]=i;

	}

	For(i,1,m){

		int u,v;

		scanf("%lld%lld",&u,&v);

		uni(u,v+n);

		uni(u+n,v);

	}

	For(i,1,n){

		if(wxp(i,i+n)){

			printf("%lld\n",n*(n-1)/2-m);

			return 0;

		}

	}

	int ls=1,rs=0;

	For(i,2,n){

		if(wxp(i,1)){

			++ls;

		}else{

			++rs;

		}

	}

	printf("%lld\n",ls*rs-m);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



long long n, m, u, v, visited[100010], a = 0, b = 0;

vector<long long> graph[100010]; bool pos = false;



void dfs(long long u) {

	for(long long i = 0; i < graph[u].size(); i++) {

		long long v = graph[u][i];

		if(visited[v] > -1) {

			pos |= (visited[u] == visited[v]);

			continue;

		}

		visited[v] = not visited[u];

		a += not visited[v], b += visited[v];

		dfs(v);

	}

}



int main() {

	memset(visited, -1, sizeof(visited));

	scanf("%lld%lld", &n, &m);

	for(long long i = 0; i < m; i++) {

		scanf("%lld%lld", &u, &v);

		graph[u].push_back(v);

		graph[v].push_back(u);

	}

	a = 1, visited[1] = 0; dfs(1);

	if(pos) printf("%lld\n", n*(n-1)/2 - m);

	else printf("%lld\n", a*b - m);

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){

    int s=0,w=1;

    char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}

    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}

    return s*w;

}

const int maxn=1e5+10;

struct edge{

    int to,nxt;

}e[maxn*2];

int head[maxn],tot,col[maxn];

ll c1,c2;

int flag;

void addedge(int u,int v){

    e[++tot].to=v;

    e[tot].nxt=head[u];

    head[u]=tot;

}

void dfs(int u,int color){

    if(flag) return;

    col[u]=color;

    if(color==1) ++c1;

    else ++c2;

    for(int i=head[u];i;i=e[i].nxt)

    {

        int v=e[i].to;

        if(!col[v]) dfs(v,3-color);

        else if(col[v]==color){

            flag=true;

            return;

        }

    }

}

ll n,m;

int main(){

    n=read(),m=read();

    for(int i=1;i<=m;i++){

        int u,v;

        u=read(),v=read();

        addedge(u,v);

        addedge(v,u);

    }

    dfs(1,1);

    if(flag) printf("%lld",1LL*n*(n-1)/2-m);

    else printf("%lld",c1*c2-m);



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <string>

#include <vector>

#include <set>

#include <algorithm>

#include <cctype>

#include <cmath>

#include <queue>

#include <map>

#include <numeric>

#include <unordered_map>

#include <iomanip>



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

#define repi(i,a,b) for(int i=int(a);i<int(b);i++)

#define all(x) (x).begin(),(x).end()



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



typedef long long ll;



using namespace std;



int n,m;

vector<vector<int>> edge;

int cnt1=0,cnt2=0;

vector<int>memo;

bool flag=0;

void dfs(int par,int node,bool oe)

{

  //cout<<par<<" "<<node<<" "<<oe<<endl;

  if(memo[node]!=-1)

  {

    if(oe!=memo[node]){flag=1;return ;}

    else return ;

  }

  if(oe)cnt1++;

  else cnt2++;

  memo[node]=(int)oe;

  for(int nn:edge[node])

  {

    if(nn!=par)

    {

      dfs(node,nn,!oe);

    }

  }

}



int main()

{

  ios::sync_with_stdio(false);

  cin.tie(0);

  //cout<<setprecision(10);

  cin>>n>>m;

  edge.resize(100001);

  memo=vector<int>(100001,-1);

  rep(i,m)

  {

    int a,b;

    cin>>a>>b;

    edge[a].push_back(b);

    edge[b].push_back(a);

  }

  dfs(-1,1,0);

  if(flag==0)

  {

    ll res=(ll)cnt1*cnt2;

    //cout<<cnt1<<" "<<cnt2<<endl;

    res-=m;

    cout<<res<<endl;

  }

  else

  {

    ll res=((ll)n*(n-1))/2;

    res-=m;

    cout<<res<<endl;

  }

  return 0;



}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <vector>

#include <set>

#include <algorithm>

#include <cctype>

#include <cmath>

#include <queue>

#include <map>

#include <numeric>

#include <unordered_map>

#include <iomanip>



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

#define repi(i,a,b) for(int i=int(a);i<int(b);i++)

#define all(x) (x).begin(),(x).end()



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



typedef long long ll;



using namespace std;



int n,m;

vector<vector<int>> edge;

int cnt1=0,cnt2=0;

vector<int>memo;

bool flag=0;

void dfs(int par,int node,bool oe)

{

  if(flag)return;

  if(memo[node]!=-1)

  {

    if(oe!=memo[node]){flag=1;return ;}

    else return ;

  }

  if(oe)cnt1++;

  else cnt2++;

  memo[node]=(int)oe;

  for(int nn:edge[node])

  {

    if(nn!=par)

    {

      dfs(node,nn,!oe);

    }

  }

}



int main()

{

  ios::sync_with_stdio(false);

  cin.tie(0);

  cin>>n>>m;

  edge.resize(n+1);

  memo=vector<int>(n+1,-1);

  rep(i,m)

  {

    int a,b;

    cin>>a>>b;

    edge[a].push_back(b);

    edge[b].push_back(a);

  }

  dfs(-1,1,0);

  if(flag==0)

  {

    ll res=(ll)cnt1*cnt2;

    res-=m;

    cout<<res<<endl;

  }

  else

  {

    ll res=((ll)n*(n-1))/2;

    res-=m;

    cout<<res<<endl;

  }

  return 0;



}


// Fastest known solution for this problem: