CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a = a[::-1]
b = b[::-1]
ans = 0
for i, bi in enumerate(b):
    ans += min(a[i], b[i])
    remain = max(0, b[i] - a[i])
    ans += min(a[i + 1], remain)
    a[i + 1] = max(0, a[i + 1] - remain)
print(ans)

# Optimized solution
n = int(eval(input()))
A = list(map(int, input().split()))[::-1]
B = list(map(int, input().split()))[::-1]
ans = 0

for i, b in enumerate(B):
    ans += min(A[i], b)
    remain = max(0, b - A[i])
    ans += min(A[i + 1], remain)
    A[i + 1] = max(0, A[i + 1] - remain)

print(ans)
# Original solution
def main():
    import sys
    input = sys.stdin.readline #文字列をsplit()しない場合s=s[:-2]が必要

    n=int(eval(input()))
    A=[int(_) for _ in input().split()]
    sum_a=sum(A)
    B=[int(_) for _ in input().split()]
    for i in range(n):
        s=max(B[i]-A[i],0)
        A[i]-=min(A[i],B[i])
        A[i+1]-=min(A[i+1],s)
    print((sum_a-sum(A)))

if __name__=='__main__':
    main()

# Optimized solution
from sys import stdin
def main():
    input=stdin.readline 

    n=int(eval(input()))
    A=[int(_) for _ in input().split()]
    sum_a=sum(A)
    B=[int(_) for _ in input().split()]
    for i in range(n):
        s=max(B[i]-A[i],0)
        A[i]-=min(A[i],B[i])
        A[i+1]-=min(A[i+1],s)
    print((sum_a-sum(A)))

if __name__=='__main__':
    main()
# Original solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    if a[i] <= b[i]:
        if a[i]+a[i+1] > b[i]:
            all_enemy = a[i] + a[i + 1]
            ans += b[i]
            a[i+1] = a[i]+a[i+1] - b[i]
        else:
            all_enemy = a[i] + a[i + 1]
            ans += all_enemy
            a[i+1] = 0
    else:
        ans += b[i]

print(ans)

# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    if a[i] <= b[i]:
        all_enemy = a[i] + a[i + 1]
        if all_enemy > b[i]:
            ans += b[i]
            a[i+1] = all_enemy - b[i]
        else:
            ans += all_enemy
            a[i+1] = 0
    else:
        ans += b[i]

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = 0
ai = 0
bi = 0
while 1:
    if max(b) == 0:
        break
    if a[ai] < b[bi]:
        ans += a[ai]
        b[bi] -= a[ai]
        a[ai] = 0
        ai += 1
    elif a[ai] == b[bi]:
        ans += a[ai]
        b[bi] = 0
        a[ai] = 0
        ai += 1
        bi += 1
    else:
        ans += b[bi]
        a[ai] -= b[bi]
        b[bi] = 0
        if ai > bi:
            bi += 1
        else:
            ai += 1
            bi += 1
 #   print(a)
 #   print(b)
 #   print(ai,bi)
    if ai >= n+1 or bi >= n:
        break
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = 0
"""
ai = 0
bi = 0
while 1:
    if max(b) == 0:
        break
    if a[ai] < b[bi]:
        ans += a[ai]
        b[bi] -= a[ai]
        a[ai] = 0
        ai += 1
    elif a[ai] == b[bi]:
        ans += a[ai]
        b[bi] = 0
        a[ai] = 0
        ai += 1
        bi += 1
    else:
        ans += b[bi]
        a[ai] -= b[bi]
        b[bi] = 0
        if ai > bi:
            bi += 1
        else:
            ai += 1
            bi += 1
 #   print(a)
 #   print(b)
 #   print(ai,bi)
    if ai >= n+1 or bi >= n:
        break
print(ans)
"""
for i in range(n):
    if b[i] >= a[i] + a[i+1]:
        ans += a[i] + a[i+1]
        a[i+1] = 0
    else:
        if b[i] >= a[i]:
            ans += b[i]
            a[i+1] -= (b[i]-a[i])
        else:
            ans += b[i]
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
for i in range(n):
    if a[i] < 0:
        a[i] = 0
    if i == n-1:
        if  b[i] <= a[i]+a[i+1]:
            count += b[i]
        else:
            count += a[i]+a[i+1]
    else:
        if b[i] <= a[i]:
            count += b[i]
        else:
            count += a[i]
            if b[i]-a[i] > a[i+1]:
                count += a[i+1]
            else:
                count += b[i]-a[i]
            a[i+1] -= b[i]-a[i]
print(count)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
for i in range(n):
    if i == n-1:
        if  b[i] <= a[i]+a[i+1]:
            count += b[i]
        else:
            count += a[i]+a[i+1]
    else:
        if b[i] <= a[i]:
            count += b[i]
        else:
            count += a[i]
            if b[i]-a[i] > a[i+1]:
                count += a[i+1]
                a[i+1] = 0
            else:
                count += b[i]-a[i]
                a[i+1] -= b[i]-a[i]
print(count)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
for i in range(n):
    if i == n-1:
        if  b[i] <= a[i]+a[i+1]:
            count += b[i]
        else:
            count += a[i]+a[i+1]
    else:
        if b[i] <= a[i]:
            count += b[i]
        else:
            count += a[i]
            if b[i]-a[i] > a[i+1]:
                count += a[i+1]
                a[i+1] = 0
            else:
                count += b[i]-a[i]
                a[i+1] -= b[i]-a[i]
print(count)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
count = 0
for i in range(n):
    if b[i] <= a[i]:
        count += b[i]
    else:
        p = b[i]-a[i]
        count += a[i]
        if p > a[i+1]:
            count += a[i+1]
            a[i+1] = 0
        else:
            count += p
            a[i+1] -= p
print(count)
# Original solution

def main():
	N = int(eval(input())) 
	A = [int(f) for f in input().split()]
	B = [int(f) for f in input().split()]
	
	m = 0
	for i in range(N):
		while A[i] > 0 and B[i] > 0:
			A[i] -= 1
			B[i] -= 1
			m += 1
		if B[i] > 0:
			while A[i+1] > 0 and B[i] > 0:
				A[i+1] -= 1
				B[i] -= 1
				m += 1
	
	print(m)

if __name__ == "__main__":
	main()

# Optimized solution

def main():
	N = int(eval(input())) 
	A = [int(f) for f in input().split()]
	B = [int(f) for f in input().split()]
	
	m = 0
	for i in range(N):
		A[i] = A[i] - B[i]
		m += B[i]
		if A[i] < 0:
			B[i] = -A[i]
			m += A[i]
			A[i] = 0
		else:
			continue
		if B[i] > 0:
			A[i+1] = A[i+1] - B[i]
			m += B[i]
			if A[i+1] < 0:
				B[i] = -A[i+1]
				m += A[i+1]
				A[i+1] = 0
	
	print(m)

if __name__ == "__main__":
	main()
# Original solution
n = int(eval(input()))
alis = list(map(int, input().split()))
blis = list(map(int, input().split()))
ans = 0
for i in range(n):
    if alis[i] + alis[i+1] > blis[i]:
        ans += blis[i]
        alis[i+1] = alis[i+1] - max(blis[i] - alis[i], 0)
    else:
        ans += alis[i] + alis[i+1]
        alis[i+1] = 0
print(ans)

# Optimized solution
n = int(eval(input()))
alis = list(map(int, input().split()))
blis = list(map(int, input().split()))
ans = 0
cross = 0
for i in range(n):
    front = min(alis[i]-cross, blis[i])
    cross = min(alis[i+1], blis[i]-front)
    ans += front + cross
print(ans)
# Original solution
n=int(eval(input()))
monsters=[int(x) for x in input().split(' ')]
powers=[int(x) for x in input().split(' ')]
ans=0
for i in range(n):
	t=min(monsters[i],powers[i])
	ans+=t
	t2=min(monsters[i+1],powers[i]-t)
	ans+=t2
	monsters[i+1]-=t2
print(ans)

# Optimized solution
n=int(eval(input()))
A=[int(x) for x in input().split(' ')]
B=[int(x) for x in input().split(' ')]
ans=0
for i in range(n):
	if (A[i]>=B[i]):
		ans+=B[i]
	else:
		ans+=A[i]
		B[i]-=A[i]

		if (A[i+1]>=B[i]):
			ans+=B[i]
			A[i+1]-=B[i]
		else:
			ans+=A[i+1]
			A[i+1]=0
print(ans)
# Original solution
N = int(eval(input()))
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
 
ans = 0
for i in range(N):
    d = min(A[i], B[i])
    ans += d
    A[i] -= d
    B[i] -= d
    d = min(A[i + 1], B[i])
    ans += d
    A[i + 1] -= d
    B[i] -= d
    
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0 

for i in range(N): 
    d = min(A[i], B[i]) 
    ans += d 
    A[i] -= d 
    B[i] -= d 
    d = min(A[i + 1], B[i]) 
    ans += d 
    A[i + 1] -= d 
    B[i] -= d 

print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(N):
    if A[i] >= B[i]:
        ans += B[i]
        A[i] -= B[i]
    else:
        ans += A[i]
        B[i] -= A[i]
        A[i] = 0
        if A[i + 1] >= B[i]:
            ans += B[i]
            A[i + 1] -= B[i]
        else:
            ans += A[i + 1]
            B[i] -= A[i + 1]
            A[i + 1] = 0
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(N):
    if A[i] >= B[i]:
        ans += B[i]
    else:
        ans += A[i]
        B[i] -= A[i]
        if A[i + 1] >= B[i]:
            ans += B[i]
            A[i + 1] -= B[i]
        else:
            ans += A[i + 1]
            A[i + 1] = 0
print(ans)
# Original solution
N = int(eval(input()))
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

St = sum(A)
for T in range(0,N):
    if A[T]+A[T+1]<= B[T]:
        A[T] = 0
        A[T+1] = 0
    if A[T]<=B[T]<A[T]+A[T+1]:
        A[T+1] = A[T+1]-(B[T]-A[T])
        A[T] = 0
    if B[T]<A[T]:
        A[T] = A[T]-B[T] 
print((St-sum(A)))

# Optimized solution
N = int(eval(input()))
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

Pre = sum(A)
for T in range(0,N):
    if A[T]<=B[T]:
        A[T+1] = max(A[T+1]-(B[T]-A[T]),0)
        A[T] = 0
    else:
        A[T] -= B[T]
Aft = sum(A)
print((Pre-Aft))
# Original solution
n=int(eval(input()))
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
ans=0
for i in range(n-1,-1,-1): #勇者を後ろから順にみていく
 if arr1[i+1]>=arr2[i]: #i番目の勇者がi+1番目の町のモンスターしか倒せないとき
   ans+=arr2[i]
   continue
 else: #i番目の勇者がi番目の町のモンスターも倒す余裕があるとき
   ans+=arr1[i+1]
   arr2[i]-=arr1[i+1]
   if arr1[i]>arr2[i]: #i番目の勇者がi番目の町のモンスターをすべて倒せないとき
     ans+=arr2[i]
     arr1[i]-=arr2[i] #i番目の勇者が倒せなかったモンスターの数を計算する
   else:  #i番目の勇者がi番目の町のモンスターもすべて倒せるとき
     ans+=arr1[i]
     arr1[i]=0
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans, surplus = 0, 0
for i in range(N):
    tmp = min(A[i], surplus)
    ans += tmp
    A[i] -= tmp
    if B[i] > A[i]:
        ans += A[i]
        surplus = B[i] - A[i]
    else:
        ans += B[i]
        surplus = 0
tmp = min(A[N], surplus)
ans += tmp
print(ans)
# Original solution
#ABC-136-C
N = int(eval(input()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
hunted_monsters = 0

for i in range(N):
    #勇者iが街iのモンスターを全て倒しても余力がある場合
    if A[i] < B[i]:
        B[i] -= A[i]
        hunted_monsters += A[i]
        A[i] = 0
        #街i+1のモンスターも全て倒せる場合
        if A[i+1] <= B[i]:
            B[i] -= A[i+1]
            hunted_monsters += A[i+1]
            A[i+1] = 0
        #街i+1のモンスターを一部倒せる場合
        else:
            A[i+1] -= B[i]
            hunted_monsters += B[i]
            B[i] = 0
    #勇者iが街iのモンスターの一部(もしくはぴったり全て)倒して余力がない場合
    else:
        A[i] -= B[i]
        hunted_monsters += B[i]
        B[i] = 0

print(hunted_monsters)
        

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(N):
    # 勇者に余力がある場合
    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
        else:
            ans += B[i]
            A[i+1] -= B[i]
    # 勇者に余力がない場合
    else:
        ans += B[i]
print(ans)
# Original solution
import sys
sys.setrecursionlimit(10**9)

N, M = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)

# 0は未着色を表す
color = [0] * N


# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

        if color[to] == 0 and not dfs(to, -c):
            return False

    return True


print((N * (N - 1) // 2 - M if not dfs(0, 1) else color.count(1) * color.count(-1) - M))


# Optimized solution
# 忘れないように
import sys
sys.setrecursionlimit(10**9)
N, M = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)


# 0は未着色を表す
color = [0] * N


# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

        if color[to] == 0 and not dfs(to, -c):
            return False

    return True


Bipartite = dfs(0, 1)

if Bipartite:
    White = color.count(1)
    Black = color.count(-1)
    print((White * Black - M))

else:
    print((N * (N - 1) // 2 - M))
# Original solution
N,M=list(map(int,input().split()))
graph=[[] for _ in range(N)]
table=[[0]*N for _ in range(N)]

for _ in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)
    table[a][b]=1
    table[b][a]=1

def steps(a,b,cnt=0):
    global flag
    global ans
    if cnt==3:
        if a!=b and not table[a][b]: 
            graph[a].append(b)
            graph[b].append(a)
            table[a][b]=1
            table[b][a]=1
            flag=True
            ans=ans+1
        return

    for nb in graph[b]:
        steps(a,nb,cnt+1)

flag=True
ans=0
while flag:
    flag=False
    for i in range(N):
        steps(i,i)
print(ans)

# Optimized solution
import sys
sys.setrecursionlimit(10**7)
N,M=list(map(int,input().split()))
graph=[[] for _ in range(N)]
color=[-1]*N
for _ in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    graph[a].append(b)
    graph[b].append(a)

def steps(v,col=0):
    color[v]=col
    for nv in graph[v]:
        if color[nv]!=-1:
            if color[nv]==col: return False
            continue
        if not steps(nv,1-col): return False
    return True

flag=True
for v in range(N):
    if color[v]!=-1: continue
    if not steps(v): flag=False

if flag:
    tmp=color.count(0)
    print((tmp*(N-tmp)-M))
else:
    print((N*(N-1)//2-M))
# Original solution
from collections import deque
n, m = list(map(int, input().split()))
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x)-1 for x in input().split()]
    connect[a].append(b)
    connect[b].append(a)
 
color = [-1]*n
color[0] = 0
explored = {0}
next = deque([0])
exploring =deque()
Yes = True
 
while next:
    now = next.popleft()
    exploring.extend(connect[now])
    while exploring:
        a = exploring.popleft()
        if color[a] == -1:
            color[a]=(color[now]+1)%2
        elif color[a] == (color[now]+1)%2:
            pass
        else:
            Yes = False
        if a not in explored:
            next.append(a)
        explored.add(a)
 
 
 
if Yes:
    s=sum(color)
    print((s*(n-s)-m))
else:
    print((n*(n-1)//2-m))

# Optimized solution
from collections import deque
n, m = list(map(int, input().split()))
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x)-1 for x in input().split()]
    connect[a].append(b)
    connect[b].append(a)
color = [-1]*n
color[0] = 0
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
if Yes:
    s=sum(color)
    print((s*(n-s)-m))
else:
    print((n*(n-1)//2-m))
# Original solution
from collections import deque
n, m = list(map(int, input().split()))
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x)-1 for x in input().split()]
    connect[a].append(b)
    connect[b].append(a)
color = [-1]*n
color[0] = 0
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != (color[now]+1)%2:
                Yes = False
            continue
        color[a] = (color[now]+1)%2
        next.append(a)
if Yes:
    s=sum(color)
    print((s*(n-s)-m))
else:
    print((n*(n-1)//2-m))

# Optimized solution
from collections import deque
n, m = list(map(int, input().split()))
connect = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(x)-1 for x in input().split()]
    connect[a].append(b)
    connect[b].append(a)
color = [-1]*n
color[0] = 0
next = deque([0])
Yes = True
while next:
    now = next.popleft()
    C = (color[now]+1)%2
    for a in connect[now]:
        if color[a] != -1:
            if color[a] != C:
                Yes = False
            continue
        color[a] = C
        next.append(a)
if Yes:
    s=sum(color)
    print((s*(n-s)-m))
else:
    print((n*(n-1)//2-m))
# Original solution
N,M=list(map(int,input().split()))
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
if dist[0]==-1:
    print((N*(N-1)//2-M))
else:
    odd=dist.count(1)
    even=dist.count(0)
    print((odd*even-M))

# Optimized solution
N,M=list(map(int,input().split()))
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=list(map(int,input().split()))
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
flag=False
while len(check)>0:
    if flag:
        break
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
            break
if dist[0]==-1:
    print((N*(N-1)//2-M))
else:
    odd=dist.count(1)
    even=dist.count(0)
    print((odd*even-M))
# Original solution
import sys
sys.setrecursionlimit(10**7)

N, M = list(map(int,input().split()))

michi = [[] for i in range(N)]
for i in range(M):
  tempa, tempb = list(map(int,input().split()))
  michi[tempa-1].append(tempb-1)
  michi[tempb-1].append(tempa-1)
#print(michi)
  
colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for to in michi[v]:
    if colors[to] == color:
      return False
    if colors[to] == 0 and not dfs(to,-color):
      return False
  return True

if dfs(0,1):
  a = colors.count(1)
  b = colors.count(-1)
  #print(colors)
  print((a*b-M))
else:
  print((N*(N-1)//2 - M))

# Optimized solution
import sys
sys.setrecursionlimit(10**7)

N,M = list(map(int,input().split()))
edge = [[] for _ in range(N)]
for i in range(M):
  a,b = list(map(int,input().split()))
  a-=1;b-=1
  edge[a].append(b)
  edge[b].append(a)
#print(edge)
colors = [0 for i in range(N)]

def dfs(v,color):
  colors[v] = color
  for u in edge[v]:
    if colors[u] == color:
      return False
    if colors[u] == 0 and not dfs(u, -color):
      return False
  return True

#print(dfs(0,1),colors)
if dfs(0,1): #もし二部グラフなら
  one = 0; zero = 0
  for x in colors:
    if x == 1:
      one += 1
    else:
      zero += 1
  ans = one*zero-M
else:
  ans = N*(N-1)//2-M
print(ans)
# Original solution
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = list(map(int, input().split()))
 
# 隣接リスト
l = [[] for i in range(N+1)]
for i in range(M):
    a,b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

def func(v,c):
    if nodes_color[v] == c:
        return True
    if nodes_color[v] == -c:
        return False
    
    if nodes_color[v] == 0:
        nodes_color[v] = c
    for node in l[v]:
        if not func(node, -c):
            return False
    
    return True

chk = func(1,1)

if chk:
    b,w = list(Counter(list(nodes_color.values())).values())
    print((int(b*w-M)))
else:
    print((int(N*(N-1)/2-M)))

# Optimized solution
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = list(map(int, input().split()))
 
# 隣接リスト
l = [[] for i in range(N+1)] 
for i in range(M):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    b,w = list(Counter(list(nodes_color.values())).values())
    print((int(b*w-M)))
else:
    print((int(N*(N-1)/2-M)))
# Original solution
from collections import deque

n, m = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
flag = True
color = [-1] * n
que = deque()
que.append((0,0))
while que:
    u, c = que.popleft()
    if color[u] == -1:  # 未探索の時
        color[u] = c
        for e in g[u]:
            que.append((e, c ^ 1))  # ^はxor
    else:
        if color[u] != c:
            flag = False
            break
if flag:
    w = len([i for i in color if i == 0])
    ans = w * (n - w) - m
else:
    ans = (n * (n - 1) // 2 - m)
print(ans)

# Optimized solution
import sys
sys.setrecursionlimit(10**6)


def dfs(u, c):
    color[u] = c
    for v in g[u]:
        if color[v] != -1:
            if color[v] == c:
                return False
        else:
            if not dfs(v, c ^ 1):
                return False
    return True


n, m = list(map(int, input().split()))
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

flag = True
color = [-1] * n
for i in range(n):
    if color[i] == -1:
        if not dfs(i, 0):
            flag = False
            break
if flag:
    w = color.count(0)
    ans = w * (n - w) - m
else:
    ans = (n * (n - 1) // 2 - m)
print(ans)