Harryxun/stf_run huggingface dataset:
n, m = list(map(int, input().split()))

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append(a, b, c)
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)


### FIXED CODE ###

n, m = list(map(int, input().split()))

import numpy as np
dists = np.ones((n + 1, n + 1)) * (10 ** 6)
edges = []
for _ in range(m):
    a, b, c = list(map(int, input().split()))
    dists[a, b] = dists[b, a] = c
    edges.append((a, b, c))
for i in range(1, n + 1):
    dists[i, i] = 0
for i in range(1, 1 + n):
    dists = np.minimum(dists, dists[i: i + 1] + dists[:, i: i + 1])
cnt = 0
for a, b, c in edges:
    if dists[a, b] < c:
        cnt += 1

print(cnt)
N, X = [int(_) for _ in input().split()]
x = [int(_) for _ in input().split()]

def gcdList(numbers):
    if len(numbers) == 1:
        return abs(numbers[0])
    if len(numbers) == 2:
        return gcd(numbers[0], numbers[1])
    else:
        return gcdList([gcd(numbers[0], numbers[1])] + numbers[2:])

def gcd(p, q):
    if p < 0:
        return gcd(-p, q)
    if q < 0:
        return gcd(p, -q)
    if q > p:
        return gcd(q, p)
    if p % q == 0:
        return q
    else:
        return gcd(q, p % q)

print(gcdList([_ - X for _ in x]))

### FIXED CODE ###

N, X = [int(_) for _ in input().split()]
xs = [abs(int(_) - X) for _ in input().split()]

def gcd(p, q):
    while q != 0:
        p, q = q, p % q
    return p

y = xs[0]
for i in range(N):
    if xs[i] % y != 0:
        y = gcd(y, xs[i])

print(y)
N, Q = input().split(" ")
N, Q = int(N), int(Q)
S = input()
s = S.replace("AC", "__")
counts = []
for i in range(Q):
    li, ri = [int(lr) for lr in input().split(" ")]
    counts[i] = s[li-1, ri].count("__")

print(max(counts))

### FIXED CODE ###

N, Q = [int(nq) for nq in input().split(" ")]
S = input()
t = [0] * (N)
for i in range(1, N):
  t[i] = t[i-1] + (1 if (S[i-1] == "A" and S[i] == "C") else 0)
for _ in " " * Q:
  l, r = [int(lr) for lr in input().split(" ")]
  print(t[r-1]-t[l-1])
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

#define rep(i, a, n) for(int i = a; i < (n); ++i)
#define ll long long

template<typename T>
bool isPrime(T x) {
  if (x == 1) return false;
  for (int i = 2; i <= sqrt(x); i += 2) {
    if (x % i == 0) return false;
  }
  return true;
}

template<typename T>
T gcd(T n, T m) {
  while (m != 0) {
    n %= m;
    swap(n, m);
  }
  return n;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll a, b;
  cin >> a >> b;
  
  ll x = gcd(a, b);
  ll ans = 1;
  for (int i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      if (isPrime(i)) {
       ++ans;
       if (i * i != x) {
         if (isPrime(x / i)) ++ans;
       }
      }
    }
  }
  cout << ans << endl;
}

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
ni = lambda : int(ns())
na = lambda : map(int, stdin.readline().split())

def divi(n):
  res = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      res.append(i)
      if i != n // i:
        res.append(n // i)
  return res

def isprime(n):
  if n == 2:
    return True
  if n % 2 == 0 or n < 2:
    return False
  for i in range(3, int(n**0.5)+1, 2):
    if (n % i == 0):
      return False
  return True

def main():
  a, b = sorted(na())
  x = divi(a)
  cnt = 1
  for bb in divi(b):
    if bb in x and isprime(bb):
      cnt += 1
  print(cnt)
main()
n,k = map(int,input().split())
p = list(int,input())
print(sum(p[:k])


### FIXED CODE ###

# -*- coding: utf-8 -*-
a = str(input())
 
if 'a' <= a <= 'z':
  print('a')
if 'A' <= a <= 'Z':
  print('A')
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def city_saver(a, b):
    monster = 0
    for i in range(len(b)):
        monster += min(a[i], b[i])
        if(a[i]<b[i]):
            monster += min(b[i]-a[i], a[i+1])
            a[i+1] -= min(b[i]-a[i], a[i+1])
    return monster

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(city_saver(a, b))

if __name__ == "__main__":
    try:
    main()


### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def city_saver(a, b):
    monster = 0
    for i in range(len(b)):
        monster += min(a[i], b[i])
        if(a[i]<b[i]):
            monster += min(b[i]-a[i], a[i+1])
            a[i+1] -= min(b[i]-a[i], a[i+1])
    return monster

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(city_saver(a, b))

if __name__ == "__main__":
    main()
K, S = map(int, input().split())

cnt = 0
for x, y, z in range(K):
  if x+y+z == S:
    cnt += 1
print(cnt)    

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if 0 <= z and z <= K:
      cnt += 1
print(cnt)
a, b = input().split()
c = 0
for i in range(a, b+1):
  if i[0] == i[4] and i[1] == i[3]:
    c += 1
print(c)

### FIXED CODE ###

a, b = map(int, input().split())
c = 0
for i in range(a, b+1):
    i = str(i)
    if i[0] == i[4] and i[1] == i[3]:
        c += 1
print(c)
X,Y=list(map(int,input().split()))

import sys
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
  print(0)
  sys.exit()

x=(2*Y-X)//3
y=(2*X-Y)//3
#(x+y)Cxを求める
fac=[0 for i in range(x+y+1)]
inv=[0 for i in range(x+y+1)]
finv=[0 for i in range(x+y+1)]
#初期条件
p=1000000007
fac[0]=fac[1]=1
inv[1]=1
finv[0]=finv[1]=1
#テーブルの作成
for i in range(2,x+y+1):
  fac[i]=fac[i-1]*i%p
  #p=(p//a)*a+(p%a) a^(-1)=-(p//a)*(p%a)^(-1)
  inv[i]=(-(p//i)*inv[p%i])%p
  finv[i]=finv[i-1]*inv[i]%p
#求める

print((fac[x+y]*finv[x]%p)*finv[y]%p)




### FIXED CODE ###

X,Y=list(map(int,input().split()))

import sys
if (2*Y-X)%3!=0 or (2*X-Y)%3!=0:
  print(0)
  sys.exit()
if (2*Y-X)<0 or (2*X-Y)<0:
  print(0)
  sys.exit()
x=(2*Y-X)//3
y=(2*X-Y)//3
#(x+y)Cxを求める
fac=[0 for i in range(x+y+1)]
inv=[0 for i in range(x+y+1)]
finv=[0 for i in range(x+y+1)]
#初期条件
p=1000000007
fac[0]=fac[1]=1
inv[1]=1
finv[0]=finv[1]=1
#テーブルの作成
for i in range(2,x+y+1):
  fac[i]=fac[i-1]*i%p
  #p=(p//a)*a+(p%a) a^(-1)=-(p//a)*(p%a)^(-1)
  inv[i]=(-(p//i)*inv[p%i])%p
  finv[i]=finv[i-1]*inv[i]%p
#求める

print((fac[x+y]*finv[x]%p)*finv[y]%p)
s = input() 
answer1 = '10'*5000 
answer2 = '01'*5000 

count1 = 0
for i in range(len(s)):
    if s[i] != answer1[i]:
        count1 += 1

count2 = 0
for i in range(len(s)):
    if s[i] != answer2[i]:
        count2 += 1

print(count1) if count1 < count2 else print(count2)


### FIXED CODE ###

s = input() 
answer1 = '10'*50000
answer2 = '01'*50000 

count1 = 0
for i in range(len(s)):
    if s[i] != answer1[i]:
        count1 += 1

count2 = 0
for i in range(len(s)):
    if s[i] != answer2[i]:
        count2 += 1

print(count1) if count1 < count2 else print(count2)
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
 
def isfeasible(L):
  k = 0
  for i in range(N):
    a = A[i]
    if a < L:
      break
    if a%L == 0:
      dk = a//L - 1
    else:
      dk = a//L
    k += dk
    if k > K:
      return False
  return True
 
l = 0
r = A[0]

while r-l>0:
  L = (r+l)//2
  if isfeasible(L):
    r = L
  else:
    l = L+1
print(r)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
 
def isfeasible(L):
  k = 0
  for a in A:
    if a < L:
      break
    if a%L == 0:
      dk = a//L - 1
    else:
      dk = a//L
    k += dk
    if k > K:
      return False
  return True
 
l = 0
r = A[0]

while r-l>1:
  L = (r+l)//2
  if isfeasible(L):
    r = L
  else:
    l = L
print(r)
import collections

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)

for i in range(n):
  print(c[a[i]])

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)

for i in range(n-1):
  print(c[i+1])

print("0")
L,R = map(int, input().split())
MIN = 2019
for i in range(L,R):
    for j in range(i+1, R+1):
        mod = ij % 2019

        if MIN > mod:
            MIN = mod
 
print(MIN)

### FIXED CODE ###

N,A,B = map(int, input().split())
if N*A >= B:
    print(B)
else:
    print(N*A)
attack=list(map(int,input().split()))
damage=list(map(int,input().split()))
A=0

N=attack[0]
K=attack[1]
damage.sort(reverse=True)
#print(damage)
if N>K:
  for i in range(K):
    del damage[i]

  for i in range(N-K):
    A+=damage[i]
  print(A)

else:
  print(0)  

### FIXED CODE ###

attack=list(map(int,input().split()))
damage=list(map(int,input().split()))
A=0

N=attack[0]
K=attack[1]
damage.sort(reverse=True)

if N>K:
  del damage[:K]
  print(sum(damage))

else:
  print(0)
n,m=map(int,input().split())
lr=[list(map(int,input().split())) for i in range(m)]
l=[0]*n
for l,r in lr:
  for t in range(l,r+1):
    l[t-1]+=1
ans=0
for ll in l:
  if ll==m:
    ans+==1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
for i in range(m-1):
  x,y=map(int,input().split())
  l=max(l,x)
  r=min(r,y)
print(r-l+1 if l<=r else(0))
n, k = map(int, input().split())
s = input()
memo = []
c = 0
ps = ''
lens = len(s) - 1
b = 0
if s[0] == '1':
    b = 1

for i in range(lens + 1):
    if s[i] != ps:
        memo.append(c)
        c = 1
        ps = s[i]
        if i == lens:
            memo.append(1)
        continue
    if i == lens:
        memo.append(c+1)
    c += 1
    ps = s[i]

sum = sum(memo[: k * 2 + b + 1])
temp = [sum]
memo.append(0)
# print(memo)
# print(len(memo))
for i in range(0, len(memo) - 2 * k  - 1, 2):
    sum = sum - memo[i] - memo[i + 1] + memo[i + 2 * k  + 1] + memo[i + 2 * k + 2]
    temp.append(sum)
# print(temp)
print(max(temp))


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
memo = []
c = 0
ps = ''
lens = len(s) - 1
b = 0
if s[0] == '1':
    b = 1

for i in range(lens + 1):
    if s[i] != ps:
        memo.append(c)
        c = 1
        ps = s[i]
        if i == lens:
            memo.append(1)
        continue
    if i == lens:
        memo.append(c+1)
    c += 1
    ps = s[i]

if  len(memo) < k * 2 + b + 1:
    print(sum(memo))
else:
    sumi = 0
    sumi = sum(memo[: k * 2 + b + 1])
    temp = [sumi]
    memo.append(0)
    # print(memo)
    # print(len(memo))
    for i in range(b, len(memo) - 2 * k  - 1, 2):
        last = 0
        if i + 2 * k + 2 <= len(memo) - 1:
            last = memo[i + 2 * k + 2]
        sumi = sumi - memo[i] - memo[i + 1] + memo[i + 2 * k  + 1] +last
        temp.append(sumi)
    # print(temp)
    print(max(temp))
N = int(input())

def sum_of(num): 
    list_b = []
    k = 0
    while num > 0:
        list_b.append(num%10)
        num //= 10
    for i in range(len(list_b)):
        k += list_b[i]
    return k 

list_a =[]
for i in range(2,N-1):
    A = i
    B = N - i
    list_a.append(sum_of(A) + sum_of(B))
    
print(min(list_a))

### FIXED CODE ###

N = int(input())

def sum_of(num): 
    list_b = []
    k = 0
    while num > 0:
        list_b.append(num%10)
        num //= 10
    for i in range(len(list_b)):
        k += list_b[i]
    return k 

list_a =[]
if N == 2:
    print(str(2))
if N == 3:
    print(str(3))
if N >= 4:
    for i in range(2,N-1):
        A = i
        B = N - i
        list_a.append(sum_of(A) + sum_of(B))
    print(min(list_a))
import sys

a,b,k = map(int,input().split())
a1 = k-a
if a1 >=1:
  a2=b-a1
  if a2 <=0:
    a2 = 0
  a1=0
else:
  a1=a-k
  a2=b
print(f'{a1} {a2}')

### FIXED CODE ###

import sys

a,b,k = map(int,input().split())
a1 = k-a
if a1 >=1:
  a2=b-a1
  if a2 <=0:
    a2 = 0
  a1=0
else:
  a1=a-k
  a2=b
print(a1,a2)
n=int(input())
print(n.replace("1","9").replace("9","1").replace("1","a").replace("9","a"))


### FIXED CODE ###

print(input().replace("1","*").replace("9","1").replace("*","9"))
n, a, b = map(int, input().split())
ans = 2 ** n -1
val = 1
for i in range(a):
    val *= (n-i) / (i+1)
ans -= val
val = 1
for i in range(b):
    val *= (n-i) / (i+1)
ans -= val
print(int(ans % int(1e9) + 7))

### FIXED CODE ###

n, a, b = map(int, input().split())
m = int(1e9) + 7
ans = (pow(2, n, m) -1) % m
val = 1
val2 = 1
for i in range(a):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= ((val % m) * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
ans %= m
val = 1
val2 = 1
for i in range(b):
    val = (val * (n - i)) % m
    val2 = (val2 * (i + 1)) % m
ans -= ((val % m) * (pow(val2, m-2, m)))
#print(((val % m) * (pow(val2, m-2, m))))
print(ans % (int(1e9) + 7))
#Grid Repainting 2

#初期化
S = []
p = []
flag = True

#入力
H,W = map(int, input().split())
for i in range(H):
	s = input()
	s_list = list(s)
	S.append(s_list)

#計算
for i in range(0, W-1, 1):
	for j in range(0, H-1, 1):
		if S[i][j] == "#" and S[i+1][j] == "." and S[i][j+1] == "."  and S[i-1][j] == "." and S[i][j-1] == "." :
			flag = False
		

#出力
if flag == True:
	print("Yes")

else:
	print("No")

### FIXED CODE ###

#Grid Repainting 2

#初期化
S = []
p = []
flag = True

#入力
H,W = map(int, input().split())
for i in range(H):
	s = input()
	s_list = list(s)
	S.append(s_list)

#計算
for i in range(0, H-1, 1):
	for j in range(0, W-1, 1):
		if S[i][j] == "#" and S[i+1][j] == "." and S[i][j+1] == "."  and S[i-1][j] == "." and S[i][j-1] == "." :
			flag = False
		

#出力
if flag == True:
	print("Yes")

else:
	print("No")
n,r=map(input().split())
if n<10:
  r=r+100*(10-n)
print(r)

### FIXED CODE ###

n,r=map(int,input().split())
if n<10:
  r=r+100*(10-n)
print(r)
N=int(input())
S=list(input())
check=[]
for i in range(N-1):
  if S[i]==S[i+1]:
    check.append(i)
reversed(check)
for i in check:
  S.pop(i)
print(len(S))

### FIXED CODE ###

N=int(input())
S=list(input())
check=[]
for i in range(N-1):
  if S[i]==S[i+1]:
    check.append(i)
check=reversed(check)
for i in check:
  S.pop(i)
print(len(S))
s=[reversed(list(input())) for i in range(3)]
flag=True
next=0
ans=0
ans_s=["a","b","c"]
while(flag):
  if len(s[next]) >0:
    next=s[next].pop()
  else:
    ans=next
    flag=False
print(ans_s[ans])

### FIXED CODE ###

s=[list(input()) for i in range(3)]
for i in range(3):
  s[i]=list(reversed(s[i]))
flag=True
next=0
ans=0
mem_s=["a","b","c"]
ans_s=["A","B","C"]
while(flag):
  if len(s[next]) >0:
    tmp=s[next].pop()
    next=mem_s.index(tmp)
  else:
    ans=next
    flag=False
print(ans_s[ans])
import math

x1,y1,x2,y2= map(int,(input().split()))

D=(x2-x1)**2+(y2-y1)**2
d= math.sqrt(D)
print(d)

### FIXED CODE ###

import math

x1,y1,x2,y2= map(float,(input().split()))

D=(x2-x1)**2+(y2-y1)**2
d= math.sqrt(D)
print(d)
W , H, x, y、r = map(int, input().split())

if (r <= x <= W -r) and (r <= y ,= H -r):
    print("Yes")

else:
    print("No")



### FIXED CODE ###

W, H, x, y, r = map(int, input().split())

if r <= x and x <= (W - r):
    if r <= y and y <= (H - r):
        print("Yes")
    else:
        print("No")

else:
    print("No")
a,b=(map(int,input().split())+13)%15;print('Alice' if a>b else 'Bob' if a<b else 'Draw)

### FIXED CODE ###

x,y=map(int,input().split())
a = (x + 13) % 15
b = (y + 13) % 15
print('Alice' if a > b else 'Bob' if a < b else 'Draw')
import numpy as np
import sys
read = sys.stdin.buffer.read

n,m,v,p = map(int,input().split())
lis = np.array(read().split(),np.int64)



lis.sort()

def test(i):
    if n-i <= p:
        return True

    num = lis[i] + m
    li = np.zeros(n,np.int64)
    li = num-lis
    li = np.minimum(li,m)
    li[n-p+1:] = m
    if(li < 0).any():
        return False
    li[i] = 0
    x = li.sum()
    return li.sum() >= m * (v-1)

low = -1
high = n-1

while low +1 < high:
    mid = (low + high) // 2
    if test(mid):
        low = mid
    else:
        high = mid

ans = n-high

print(ans)


### FIXED CODE ###

n,m,v,p = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort(reverse=True)
ans = 0
trash = 0
for i in range(n):
    if i+1 <= p:
        ans += 1
    else:
        if lis[i] + m >= lis[p-1]:
            if (lis[i]+m)*(i-(p-1))-trash >= m * (v-(p-1)-(n-i)):
  #                 print(lis[i]+m,i-(p-1)-trash,m*(v-(p-1)-(n-i)))
                ans += 1
    if i+1 >= p:
        trash += lis[i]
print(ans)
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))
not_b10 = sorted([s for s in S if s%10 != 0])
b10 = sorted([s for s in S if s%10 == 0])
    
if sum(S)%10!=0:
    print(sum(S))
elif S ==b10:
    print(0)
else:

    print(sum(S)-not_b10[0])

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(int(input()))
nb10 = ([s for s in S if s%10 != 0])
b10  = ([s for s in S if s%10 == 0])
    
if sum(S)%10!=0:
    print(sum(S))
elif sum(S) ==sum(b10):
    print(0)
else:

    print(sum(S)-sorted(nb10)[0])
n = int(input())
a = list(map(int, input().split()))
s, ans, i = 0, 0, 0
while a[i] == 0 and i < n:
    ans += 2
    i += 1
ans = max(0, ans - 1)
if i == n:
    print(ans)
    exit()

if ans > 0:
    ans -= 1
    if abs(a[i]) == 1:
        ans += 1
        s = a[i] // abs(a[i])
else:
    s = a[0]

i += 1
for j in range(i, n):
    if abs(a[j]) > abs(s) and (a[j] == abs(a[j])) != (s == abs(s)):
        s += a[j]
    else:
        pre_s = s
        s = -1 * s // abs(s)
        ans += abs(a[j] - s + pre_s)

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans1, ans2 = 0, 0
s = 0
plus = True
for i in range(n):
    if plus:
        if s + a[i] > 0:
            s += a[i]
        else:
            ans1 += abs(1 - (s + a[i]))
            s = 1
    if not plus:
        if s + a[i] < 0:
            s += a[i]
        else:
            ans1 += abs(-1 - (s + a[i]))
            s = -1
    plus = not plus

s = 0
plus = False
for i in range(n):
    if plus:
        if s + a[i] > 0:
            s += a[i]
        else:
            ans2 += abs(1 - (s + a[i]))
            s = 1
    if not plus:
        if s + a[i] < 0:
            s += a[i]
        else:
            ans2 += abs(-1 - (s + a[i]))
            s = -1
    plus = not plus
print(min(ans1, ans2))
import math
a,b = map(int,input().split())
a_min = math.ceil(a / 0.08)
a_max = math.floor((a + 1) / 0.08)
b_min = math.ceil(b / 0.1)
b_max = math.floor((b + 1) / 0.1)

if a_max < b_min or b_max < a_min:
  print(-1)
else:
  result = b_min if a_min < b_min else a_min
  print(result)

### FIXED CODE ###

s = list(input())

if len(list(set(s))) != 1:
  print('Yes')
else:
  print('No')
n = int( input( ) )
nums = []
for i in range( n ):
	nums.append( int( input( ) ) )

g = []
val = 1
while val <= n:
	g.append( val )
	val = 3*val+1
g.reverse( )
m = len( g )
print( m )
print( " ".join( map( str, g ) ) )
cnt = 0
for i in range( m ):
	for k in range( g[i], n ):
		v = nums[k]
		j = k - g[i]
		while 0 <= j and v < nums[j]:
			nums[ j+g[i] ] = nums[j]
			j -= g[i]
			cnt += 1
			nums[ j+g[i] ] = v
print( cnt )
print( "\n".join( map( str, nums ) ) )

### FIXED CODE ###

import sys
 
def insertionSort( nums, n, g ):
    cnt = 0
    i = g
    while i < n:
        v = nums[i]
        j = i - g
        while 0 <= j and v < nums[j]:
            nums[ j+g ] = nums[j]
            j -= g
            cnt += 1
        nums[ j+g ] = v
        i += 1
    return cnt
         
def shellSort( nums, n ):
    g = []
    val = 1
    while val <= n:
        g.append( val )
        val = 3*val+1
     
    g.reverse( )
    m = len( g )
    print( m )
    print( " ".join( map( str, g ) ) )
    cnt = 0
    for i in range( m ):
        cnt += insertionSort( nums, n, g[i] )
    print( cnt )
     
n = int( sys.stdin.readline( ) )
nums = []
for i in range( n ):
    nums.append( int( sys.stdin.readline( ) ) )
 
shellSort( nums, n )
print( "\n".join( map( str, nums ) ) )
import collections
N=int(input())
A=collections.Counter(list(map(int,input().split())))
if N%2==0:
  for i in range(0,N,2):
    if i%2==0 and A[i]==0:
      pass
    elif i%2==a and A[i]==2:
      pass
    else:
        print(0);exit()
  print(2**(N//2))
else:
  for i in range(N):
    if i==0:
      if A[i]!=1:
        print(0);exit()
    elif i%2==0 and A[i]==2:
      pass
    elif i%2==1 and A[i]==0:
      pass
    else:
      print(0);exit()
  print(2**(N//2))

### FIXED CODE ###

import collections
N=int(input())
A=collections.Counter(list(map(int,input().split())))
if N%2==0:
  for i in range(0,N,2):
    if i%2==0 and A[i]==0:
      pass
    elif i%2==1 and A[i]==2:
      pass
    else:
        print(0);exit(0)
else:
  for i in range(N):
    if i==0 and A[i]==1:
      continue
    if i%2==0 and A[i]==2:
      pass
    elif i%2==1 and A[i]==0:
      pass
    else:
      print(0);exit(0)
print(pow(2,N//2,10**9+7 ))
r,g=list(map(int,input().split()))
print(2*g-r)

### FIXED CODE ###

r=int(input())
g=int(input())
print(2*g-r)
a,c=map(int,input().split())
b,d=map(int,input().split())
t=map(int,input().split())
if c<=d:
  print('NO')
elif abs(a-b)<=(c-d)*t:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

a,c=map(int,input().split())
b,d=map(int,input().split())
t=int(input())
if c<=d:
  print('NO')
else:
  if abs(a-b)<=(c-d)*t:
  	print('YES')
  else:
    print('NO')
import numpy as np
L = int(input())
N = int(input())
s = 0
for i in range(N):
    x, w = map(int, input().split())
    s += x * w
if(s == 0):
    print(0)
elif(s < 0):
    print(1)
    print(1, -s)
else:
    print(1)
    print(-1, s)

### FIXED CODE ###

L = int(input())
N = int(input())
s = 0
for i in range(N):
    x, w = map(int, input().split())
    s += x * w
if(s == 0):
    print(0)
elif(s < 0):
    print(1)
    print(1, -s)
else:
    print(1)
    print(-1, s)
a = [list(map(int,input().split())) for i in range(3)]
n = int(input())
b = [int(input() )for _ in range(n)]

print(a,n,b)
for i in range(3):
    for j in range(3):
        if a[i][j] in b:
            a[i][j] = 0

for i in range(3):
    if a[i] == [0,0,0]:
        print('Yes')
        exit()
for i in range(3):
    if a[j0][i] == 0 and a[1][i] == 0 and a[2][i] == 0:
        print('Yes')
        exit()
if a[0][0] == 0 and a[1][1] == 0 and a[2][2] == 0:
    print('Yes')
    exit()
if a[2][0] == 0 and a[1][1] == 0 and a[0][2] == 0:
    print('Yes')
    exit()
print('No')

### FIXED CODE ###

a = [list(map(int,input().split())) for i in range(3)]
n = int(input())
b = [int(input() )for _ in range(n)]

for i in range(3):
    for j in range(3):
        if a[i][j] in b:
            a[i][j] = 0

for i in range(3):
    if a[i][0] == 0 and a[i][1] == 0 and a[i][2] == 0:
        print('Yes')
        exit()
for i in range(3):
    if a[0][i] == 0 and a[1][i] == 0 and a[2][i] == 0:
        print('Yes')
        exit()
if a[0][0] == 0 and a[1][1] == 0 and a[2][2] == 0:
    print('Yes')
    exit()
if a[2][0] == 0 and a[1][1] == 0 and a[0][2] == 0:
    print('Yes')
    exit()
print('No')
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(n):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
x=[0]*n
x[0]=1
def dfs(r,node):
  for mode in edge[node]:
    if r==mode:continue
    x[mode]=1^x[node]
    dfs(node,mode)
dfs(-1,0)
print(x.count(0)*x.count(1)-m)

### FIXED CODE ###

# 二部グラフ判定
def bipartite_graph_check(n,edge):
  color = [-1] * n
  for i in range(n):
    if color[i] != -1:
      continue
    stack = [i]
    color[i] = 0
    for node in stack:
      for mode in edge[node]:
        if color[mode] == -1:
          stack.append(mode)
          color[mode] = color[node] ^ 1
        elif color[mode] == color[node]:
          return False
  #return True
  return color
n,m=map(int,input().split())
edge=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edge[a].append(b)
  edge[b].append(a)
if bipartite_graph_check(n,edge):
  color=bipartite_graph_check(n,edge)
  print(color.count(0)*color.count(1)-m)
else:
  print(n*(n-1)//2-m)