Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- Coding: utf-8 -*-
n, m = map(int, input().split())
INF = 1001001001
key_list = []
cost_list = []
for i in range(m):
  a, b = map(int, input().split())
  cost_list.append(a)
  c = list(map(int, input().split()))
  s = 0
  for j in range(b):
    s |= 1 << c[j] - 1
  key_list.append(s)
   
dp = [INF] * (1 << n)
dp[0] = 0
for s in range(1 << n):
  for i in range(m):
    t = s | key_list[i]
    cost = dp[s] + cost_list[i]
    dp[t] = min(cost, dp[t])
if dp[-1] == INF:
  ans = -1
else:
  ans = dp[-1]
print(ans)


### FIXED CODE ###

# -*- Coding: utf-8 -*-
n, m = map(int, input().split())
INF = 1001001001
key_list = []
cost_list = []
for i in range(m):
  a, b = map(int, input().split())
  cost_list.append(a)
  c = list(map(int, input().split()))
  s = 0
  for j in range(b):
    s |= 1 << c[j] - 1
  key_list.append(s)
   
dp = [INF] * (1 << n)
dp[0] = 0
for s in range(1 << n):
  for i in range(m):
    t = s | key_list[i]
    cost = dp[s] + cost_list[i]
    dp[t] = min(cost, dp[t])
if dp[-1] == INF:
  ans = -1
else:
  ans = dp[-1]
print(ans)
### BUGGY CODE ###

n=int(input())

s=[int(i) for i in input().split()]
c=0
max=0
pos=0
for i in range(n):
    c=0
    for j in range(i,n-1):
        if(s[j]>=s[j+1]):
            c+=1
        else:
            break
    if(c>max):
        max=c
    if(max>(n-i-1)):
        break
print(max)


### FIXED CODE ###

n = int(input())
values = [float(s) for s in input().split(" ")]

start = 0
ans = 0

for i in range(1,n):
    if values[i] > values[i-1]:
        start = i
    ans = max(ans,i-start)
print(ans)
### BUGGY CODE ###

def solve():
  ans = 0
  H, W = map(int, input().split())
  S = [0]*(H+2)
  S[0] = '*'*(W+2)
  S[H+1] = '*'*(W+2)
  for h in range(1,H+1):
    S[h] = '*' + input() + '*'
  L = [[0]*(W+2) for _ in range(H+2)]
  R = [[0]*(W+2) for _ in range(H+2)]
  U = [[0]*(W+2) for _ in range(H+2)]
  D = [[0]*(W+2) for _ in range(H+2)]
  for h in range(1,H+2):
    for w in range(1,W+2):
      if S[h][w]=='.':
        if S[h][w-1]=='.':
          L[h][w] = L[h][w-1]+1
        if S[h-1][w]=='.':
          U[h][w] = U[h-1][w]+1
  for h in range(H+1,0,-1):
    for w in range(W+1,0,-1):
      if S[h][w]=='.':
        if S[h][w+1]=='.':
          R[h][w] = R[h][w+1]+1
        if S[h+1][w]=='.':
          D[h][w] = D[h+1][w]+1
  total = [[0]*(W+2) for _ in range(H+2)]
  for h in range(1,H+2):
    for w in range(1,W+2):
      if S[h][w]=='.':
        total[h][w] = L[h][w]+R[h][w]+U[h][w]+D[h][w]+1
        ans = max(ans,total[h][w])
  return ans
print(solve())

### FIXED CODE ###

#import numpy as np
H, W = map(int, input().split())
S = [0]*H
counth = [[0]*W for _ in range(H)]  
countw = [[0]*W for _ in range(H)]

for i in range(H):
  S[i] = input()
  
for i in range(H):
  for j in range(W):
    if S[i][j]=='.':
      if counth[i][j]==0:
        b=False
        for k in range(j,W):
          if S[i][k]=='#':
            b = True
            break
        if b==False:
          k+=1
        #print(S[i][j:],l)
        for l in range(j,k):
          #print(i,j,l)
          counth[i][l]=k-j
      if countw[i][j]==0:
        b=False
        for k in range(i,H):
          if S[k][j]=='#':
            b=True
            break
        if b==False:
          k+=1
        #print(S[i:][j],m)
        for l in range(i,k):
          #print(i,j,l)
          countw[l][j]=k-i
      #print(i,j,count)
#print(counth,countw)
maxim = 0
for i in range(H):
  for j in range(W):
    maxim = int(max(maxim,counth[i][j]+countw[i][j]-1))
print(maxim)
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import coo_matrix

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

a = AB[::2]
b = AB[1::2]
d = [1] * (N - 1)

graph = coo_matrix((d, (a, b)), shape=(N + 1, N + 1))
takahashi, aoki = dijkstra(graph, directed=False, indices=[u, v])

print(int(aoki[takahashi < aoki].max()) - 1)

### FIXED CODE ###

import sys

read = sys.stdin.read
N, u, v, *AB = map(int, read().split())

graph = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    dist = [-1] * (N + 1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist


DU, DV = dfs(u), dfs(v)

answer = 0
for u, v in zip(DU[1:], DV[1:]):
    if u < v:
        tmp = v - 1
        if answer < tmp:
            answer = tmp

print(answer)
### BUGGY CODE ###

n,m = map(int,input().split())
a_list = list(map(int,input().split()))
for i in range(m):
 a_list[a_list.index(max(a_list))] =a_list[a_list.index(max(a_list))]//2
   
print(sum(a_list))


### FIXED CODE ###

n,m = map(int,input().split())
import math
a_list = list(map(int,input().split()))
for i in range(n):
  a_list[i] = -1 * a_list[i]
import heapq
heapq.heapify(a_list)
for j in range(m):
  
  a = heapq.heappop(a_list)
  a = math.ceil(a/2)
  heapq.heappush(a_list,a)


print(-1 * sum(a_list))
### BUGGY CODE ###

n = int(input())
L6 = []
L9 = []
for i in range(1, 100):
  num = 6 ** i
  if num <= n:
    L6.append(num)
  else:
    break
for i in range(1, 100):
  num = 9 ** i
  if num <= n:
    L9.append(num)
  else:
    break

from itertools import product
iter6 = product(range(0, 6), repeat=len(L6))
Res6 = []
for iter in iter6:
  total = 0
  counter = 0
  for num, l in zip(iter, L6):
    total += num * l
    counter += num
  if n - total >= 0:
    Res6.append([n - total, counter])
#print(Res6)

iter9 = product(range(0, 9), repeat=len(L9))
Res9 = []
for iter in iter9:
  total = 0
  counter = 0
  for num, l in zip(iter, L9):
    total += num * l
    counter += num
  if n - total >= 0:
    Res9.append([total, counter])

#print(list(product(Res6, Res9)))
Res9.sort(key = lambda x:x[0])

min_x = n
for cand6 in Res6:
  for cand9 in Res9:
    if cand6[0] - cand9[0] >= 0:
      x = cand6[0] - cand9[0] + cand6[1] + cand9[1]
      min_x = min(min_x, x)
    else:
      break
print(min_x)


### FIXED CODE ###

n = int(input())

L6 = []
for i in range(1, 100):
  if 6**i <= n:
    L6.append(6**i)
  else:
    break

L9 = []
for i in range(1, 100):
  if 9**i <= n:
    L9.append(9**i)
  else:
    break

dp = [0] * (n+1)
    
for i in range(1, n+1):
  dp[i] = dp[i-1] + 1
  for l6 in L6:
    if i - l6 >= 0:
      dp[i] = min(dp[i], dp[i - l6] + 1)
  for l9 in L9:
    if i - l9 >= 0:
      dp[i] = min(dp[i], dp[i - l9] + 1)
print(dp[n])
### BUGGY CODE ###

n = int(input())
s_list = [''.join(sorted(input())) for _ in range(n)]
s_set = set(s_list)
cnt = 0
for s in s_set:
    cnt += sum(range(s_list.count(s)))
    s_list.remove(s)
print(cnt)

### FIXED CODE ###

n = int(input())
cnt = 0
s_dic = {}
for _ in range(n):
    s = ''.join(sorted(input()))
    if s in s_dic.keys():
        s_dic[s] += 1
        cnt += s_dic[s]
    else:
        s_dic[s] = 0

print(cnt)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
flag=0
for i in range(N):
  ans*=A[i]
  if ans>10**18:
    flag=1
  
if ans==0:
  flag=0
if flag==0:
  print(ans)
else:
  print("-1")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
flag=0
for i in range(N):
  if A[i]==0:
    flag=1
sflag=0
ans=1
for i in range(N):
  ans*=A[i]
  if ans>10**18:
    sflag=1
    break
  if sflag==1:
    break
if sflag==0:
  print(ans)
elif sflag==1 and flag==1:
  print("0")
else:
  print("-1")
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
a = LIST()
count = 0
flag = 0
while flag == 0:	
	for i in range(N):
		if a[i] % (1024**2) == 0:
			a[i] /= (1024**2)
			count += 20
			break
	else:
		flag = 1
flag = 0
while flag == 0:	
	for i in range(N):
		if a[i] % 2 == 0:
			a[i] /= 2
			count += 1
			break
	else:
		flag = 1
print(count)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
a = LIST()
count = 0
flag = 0
"""
while flag == 0:
	print(a)
	for i in range(N):
		if a[i] % 2 == 0:
			a[i] = int(a[i]/2)
			count += 1
			break
	else:
		flag = 1
"""
for i in a:
    while i % 2 == 0:
        count += 1
        i /= 2
print(count)
### BUGGY CODE ###

n, x, y = map(int, input().split())
king_li = []
for i in range(1, n+1):
    for j in range(i+1,n+1):
        li = []
        li.append(abs(y-j)+abs(x-i)+1)
        li.append(j-i)
        king_li.append(min(li))
for z in range(1,n):
    print(king_li.count(z))

### FIXED CODE ###

n, x, y = map(int, input().split())
dic={}
for i in range(1, n+1):
    for j in range(i+1,n+1):
        m = min(abs(y-j)+abs(x-i)+1,j-i)
        if m in dic.keys():
            dic[m] += 1
        else:
            dic[m] =1

for z in range(1,n):
    if z in dic.keys():
        print(dic[z])
    else:
        print(0)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            ff = False
            if f:
                if i == 0:
                    tmp = float("inf")
                    break
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                        ff = True
                        break
                    if n >> j & 1:
                        ni += 1
            if ff:
                break

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                        break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break
                for wii in range(ni + 1):
                    if wn[wii] > K:
                        tmp = float("inf")

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)
candi = np.array([0] * N)

for i in range(1, N):
	j = max(0, i-K)
	candi[j:i] = dp[j:i] + np.abs(h[i] - h[j:i])
	dp[i] = candi[j:i].min()

print(dp[-1])

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.array([0] * N)
#candi = np.array([0] * N)

for i in range(1, N):
	j = max(0, i-K)
	#print()
	#candi[j:i] = dp[j:i] + np.abs(h[i] - h[j:i])
	dp[i] = (dp[j:i] + np.abs(h[i] - h[j:i])).min()
	#print('j,i=',j,i)
	#print('dp[j:i]=',dp[j:i])
	#print('np.abs(h[i] - h[j:i]) = ', np.abs(h[i] - h[j:i]) )		
	#print('candi[j:i]=',candi[j:i])
	#dp[i] = candi[j:i].min()
	#print('dp=',dp)
				
print(dp[-1])
### BUGGY CODE ###

H, W = map(int, input().split())
a = []
INF = 10**9
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
for i in range(H):
    a.append(input())

dist_map = [[INF]*W for _ in range(H)]
# 黒マスの位置を記録
black_pos = []
for i in range(H):
    for j in range(W):
        if a[i][j] == "#":
            black_pos.append([i, j])

def update(c_h, c_w, d_map, dist, q):
    if d_map[c_h][c_w] != INF:
        return
    d_map[c_h][c_w] = dist
    for dir in range(4):
        if c_h+n_i[dir] < 0 or H <= c_h+n_i[dir] or c_w+n_j[dir] < 0 or W <= c_w+n_j[dir]:
            continue
        if a[c_h+n_i[dir]][c_w+n_j[dir]] == "#":
            continue
        q.append((c_h+n_i[dir], c_w+n_j[dir], dist+1))

q = [(pos[0], pos[1], 0) for pos in black_pos]
while len(q) > 0:
    current = q.pop(0)
    current_h = current[0]
    current_w = current[1]
    dist = current[2]
    update(current_h, current_w, dist_map, dist, q)

max_dist = 0
for i in range(H):
    for j in range(W):
        if max_dist < dist_map[i][j] and dist_map[i][j] != INF:
            max_dist = dist_map[i][j]
print(max_dist)


### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)
### BUGGY CODE ###

import collections

N=int(input())
S=input()

count=0
for i in range(N-2):
    for j in range(i,N-1):
        if (S[i] != S[j]) :
            for k in range(j,N):
                if (j-i)==(k-j):
                    continue
                if (S[i]!=S[k]) and (S[j]!=S[k]):
                    count+=1
    
print(count)

### FIXED CODE ###

import collections

N=int(input())
S=input()

lenR=S.count("R")
lenG=S.count("G")
lenB=S.count("B")

count=0
for i in range(N-2):
    for j in range(i,N-1):
        k=2*j-i
        if k>=N:
            continue
        else:
            if (S[i] != S[j]) and (S[i]!=S[k]) and (S[j]!=S[k]):
                count+=1
    
print(lenR*lenG*lenB-count)
### BUGGY CODE ###

import math
a, b = list(map(int, input().split(' ')))
def gcd(l, s):
    return s if l % s == 0 else gcd(s, l % s)
g = gcd(a, b)
primes = []
if g % 2 == 0:
    primes.append(2)
def prime(n):
    for i in range(len(primes)):
        if n % primes[i] == 0:
            return False
    return True
def make():
    for i in range(3, g + 1, 2):
        if g%i == 0 and prime(i):
            primes.append(i)

make()

print(len([i for i in primes if g % i == 0]) + 1)

### FIXED CODE ###

a, b = list(map(int, input().split(' ')))
def gcd(l, s):
  return l if s == 0 else gcd(s, l % s)

temp = gcd(a, b)

ans = 0
for i in range(2,1000000):
  if temp % i == 0:
    ans += 1
    while temp % i == 0:
      temp = temp // i
  if temp == 1:
    break
if temp != 1:
  ans += 1

print(ans+1)
### BUGGY CODE ###

n,a,b = map(int,input().split())

mod = 10**9 + 7

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = pow(2,n,mod) - 1

a = comb_mod(n,a,mod)

b = comb_mod(n,b,mod)

ans = m - a - b

print(ans%mod)

### FIXED CODE ###

n,a,b = map(int,input().split())

mod = 10**9 + 7

def comb(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%mod
    for i in range(2,k+1):
        inv[i]=mod-inv[mod%i]*(mod//i)%mod
        ans=ans*(n-k+i)*inv[i]%mod
    return ans

def comb_mod(n, r, mod):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    else:
        fac = [1, 1]
        finv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fac.append(fac[-1] * i % mod)
            inv.append(-inv[mod % i] * (mod // i) % mod)
            finv.append((finv[-1] * inv[-1]) % mod)
        return int(fac[n] * finv[r] * finv[n - r] % mod)

m = pow(2,n,mod) - 1

import math
def perm(n,r):
    return (math.factorial(n)//math.factorial(n-r))

s = comb(n,a,mod)
# print(s)

t = comb(n,b,mod)
# print(t)

ans = m - s - t

print(ans%mod)
### BUGGY CODE ###

s = input()
s = [ord(i) - 97 for i in s]
t = input()
t = [ord(i) -97 for i in t]

ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

max_len = dp[-1][-1]

ans = []

i = ls
j = lt

for l in range(max_len):
    while dp[i-1][j] == max_len - l:
        i -= 1
    while dp[i][j-1] == max_len - l:
        j -= 1
    ans.append(s[i-1])
    #ans += s[i-1]

alphabet = [chr(97+i) for i in range(27)]
a = ""
for i in ans:
    a += alphabet[i]
print(a[::-1])
#print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [[0]*(lt+1) for i in range(ls+1)]

for i in range(1,ls+1):
    for j in range(1,lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

max_len = dp[-1][-1]
ans = ""

i = ls
j = lt

while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

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

a = list(map(int, input().split()))

from itertools import combinations_with_replacement
from itertools import groupby

ans = float("inf")
x =sum(a)

for i in combinations_with_replacement(range(n), m):
  m = x
  lis = list(i)
  for j, k in groupby(lis):
    m -= a[j]
    m += a[j]//(2**len(list(k)))
  ans = min(ans, m)
  
print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
A =[-a for a in A]

heapq.heapify(A)
  
for i in range(M):
  curr = -heapq.heappop(A)
  heapq.heappush(A, -(curr//2))
  
print(-sum(A))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1


d_c = {}
for i in d:
    d_c[i] = d[i] * (d[i] - 1) // 2


d_3 ={}

for i in range(n):
    b = a[i]
    count = 0
    if b not in d_3:
        for j in d:
            if j != b:
                count += d_c[j]
            else:
                count += d_c[j]*(d[j]-2)//d[j]
        d_3[b] = count
        print(count)
    else:
        print(d_3[b])

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

count = 0
for i in d:
    count += d[i] * (d[i] - 1) // 2


for i in range(n):
    b = d[a[i]]
    print(count-b+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

N,M=[int(a) for a in input().split()]
AB=[[int(a) for a in input().split()] for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

visited = [False]*N
WH = [None]*N

def dfs(curr, is_white):
    if visited[curr]:
        return WH[curr]^is_white
    WH[curr] = is_white
    visited[curr] = True
    ans = False
    for node in edges[curr]:
        ans |= dfs(node, not is_white)
    return ans

if dfs(0, True):
    print((N*(N-1))//2 - M)
else:
    nw = sum(WH)
    print(nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N,M=[int(a) for a in input().split()]
AB=[[int(a) for a in input().split()] for _ in range(M)]
edges = [[] for _ in range(N)]
for a, b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

colors = [0]*N
def dfs(curr, c):
    colors[curr] = c
    for node in edges[curr]:
        if colors[node] == colors[curr]:
            return False
        if colors[node]== 0 and not dfs(node, -c):
            return False
    return True

if not dfs(0, 1):
    print((N*(N-1))//2 - M)
else:
    WH = [c==1 for c in colors]
    nw = sum(WH)
    print(nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB]))
### BUGGY CODE ###

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

dia = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
  l, r = map(int, input().split())
  dia[l][r] += 1
  
lst = [[0]*(n+1) for i in range(n+1)]
for i in range(1, n+1):
  for j in range(i, n+1):
    lst[i][j] = lst[i][j-1] + dia[i][j]
    
for i in range(q):
  l, r = map(int, input().split())
  count = 0
  for j in range(l, r+1):
    count += lst[j][r]
  print(count)

### FIXED CODE ###

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

dia = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
  l, r = map(int, input().split())
  dia[l][r] += 1
  
lst = [[0]*(n+1) for i in range(n+1)]
for i in range(1, n+1):
  for j in range(i, n+1):
    lst[i][j] = lst[i][j-1] + dia[i][j]
    
for i in range(q):
  l, r = map(int, input().split())
  count = 0
  for j in range(l, r+1):
    count += lst[j][r]
  print(count)