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

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from copy import deepcopy
n,m = map(int,input().split())
inf = float("inf")
L = [[inf for i in range(n)] for j in range(n)]

for i in range(m):
    a,b = map(int,input().split())
    L[a-1][b-1] = 1
    L[b-1][a-1] = 1
#print(L)
cnt = 0
for i in range(n):
    for j in range(n):
        LL = deepcopy(L)
        LL[i][j] = 0
        LL[j][i] = 0
        LL = floyd_warshall(LL)
        #print(LL)
        for k in LL:
            if inf in k:
                cnt +=1
                break
print(cnt//2) 

### FIXED CODE ###

n,m = map(int,input().split())
d = []
for i in range(m):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    d.append((a,b))
#print(d)
pa = None

def root(a):
    if pa[a] == a:
        return a
    else:
        pa[a] = root(pa[a])
        return pa[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    aa = root(a)
    bb = root(b)
    if aa == bb:
        return
    pa[aa] = bb

ans = 0
for i in range(m):
    pa = [x for x in range(n)]
    for j,v in enumerate(d):
        #(i,j,v)
        if i == j:continue
        a,b = v
        unite(a,b)
    a,b = d[i]
    if not is_same(a,b):
        ans +=1
print(ans)
### BUGGY CODE ###

import itertools
 
n = int(input())
num_list = list(map(int, input().split()))
sum = 0
 
for i in itertools.combinations(num_list, 2):
    x = i[0] * i[1]
    if x > 10**9 + 7 :
        x = x % (10**9 + 7)
        sum += x
    else:
        sum += x
        
    if sum > 10**9 + 7:
        sum %= 10**9 + 7

print(sum)

### FIXED CODE ###

from itertools import accumulate

n = int(input())
a = list(map(int, input().split()))
b = list(accumulate(a))
sum = 0

for i in range(len(a)):
    sum += a[i]*(b[-1] - b[i])
    sum %= 10**9 + 7

print(sum)
### BUGGY CODE ###

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))
sum = [0]*(n+1)

for i in range(1,n+1):
  sum[i] = sum[i-1] + a[i-1]

cnt = 0
for i in range(n):
  for j in range(i+1, n+1):
    if((sum[j] - sum[i])%m == 0):
      cnt += 1
      
print(cnt)
    
    

### FIXED CODE ###

from collections import Counter
n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))
s = [0]*(n+1)
for i in range(1,n+1):
  s[i] = (s[i-1] + a[i-1])%m

cl = Counter(s).values()
ans = sum(i*(i-1)//2 for i in cl)
print(ans)
### BUGGY CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
ini_sum = sum(a)
q = int(input())
s = [0] * q

for i in range(q):
    b, c = map(int, input().split())
    counter[c] += counter[b]
    counter[b] = 0
    print(sum(key * value for key, value in counter.items()))


### FIXED CODE ###

from collections import Counter


n = int(input())
a = list(map(int, input().split()))
counter = Counter(a)
ini_sum = sum(a)
q = int(input())
s = [ini_sum] + [0] * q

for i in range(1, q+1):
    b, c = map(int, input().split())
    x = c - b
    s[i] = s[i-1] + x*counter[b]
    counter[c] += counter[b]
    counter[b] = 0

for i in range(1, q+1):
    print(s[i])
### BUGGY CODE ###

s=input()
s=s.replace('BC','D')
ans=0
while s.count('AD')>0:
    ans+=s.count('AD')
    s=s.replace('AD','DA')
print(ans)

### FIXED CODE ###

import re
s=input()
ss=s.replace('BC','D')
sss=re.split('[BC]',ss)
ans=0
for i in sss:
    acnt=0
    for g in i:
        if g=='A':
            acnt+=1
        else:
            ans+=acnt
print(ans)
### BUGGY CODE ###

class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = -(10 ** 18)  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i

N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = Max_Bit(N)
for i in range(N):
    dp.update(i+1,A[i])
for i in range(2,N + 1):
    for j in range(1, i):
        if H[i-1] >= H[j-1]:
            dp.update(i, dp.tree[j] + A[i-1])
print(dp.get_max())

### FIXED CODE ###

class Max_Bit:
    """区間の最大値のＢＩＴ

    viの更新をする。
    v1からｖiまでの最大値を取得する。
    どちらもO(logn)時間にできる

    Attributes:
        size (int): BITのサイズ
        tree (list of int): 区間の最大値を管理するための二分木
    """
    def __init__(self, n):
        """
        Args:
            n(int): BITのサイズ
        """
        self.size = n
        self.tree = [0] * (n + 1)

    def get_max(self, i=None):
        if i is None:
            i = self.size
        m = 0  # -INF
        while i > 0:
            m = max(m, self.tree[i])
            i -= i & -i
        return m

    def update(self, i, x):
        while i <= self.size:
            self.tree[i] = max(x, self.tree[i])
            i += i & -i
def main():
    """
    dp: 花iを使うとした場合の1からiまでつかった美しさの最大値
    短い花から更新する

    """
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = Max_Bit(N)
    sort_H_i = sorted((h, i) for i, h in enumerate(H))
    for h, i in sort_H_i:
        dp.update(i+1,dp.get_max(i) + A[i])
    print(dp.get_max())

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

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

def main():
    n=n0()
    a=n1()

    from math import factorial
    def comb(n):
        if n<=1:
            return 0
        if n==2:
            return 1
        return factorial(n)//(factorial(2)*factorial(n-2))

    c=[a.count(i) for i in range(1,n+1)]
    d=[comb(m) for m in c]
    s=sum(d)

    for i in range(n):
        print(s-d[a[i]-1]+comb(c[a[i]-1]-1))
if __name__ == '__main__':
	main()

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n=n0()
a=n1()

def comb(n):
    if n<=1:
        return 0
    if n==2:
        return 1
    return (n*(n-1))//2

from collections import Counter
c=Counter(a)
# print(c)
d={i:comb(j) for i,j in c.items()}
# print(d)
s=sum(d.values())
# print(s)

for i in a:
    print(s-d[i]+comb(c[i]-1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    ans = 0
    while len(aa) > 1:
        mn = 10**10
        mi = -1
        for i in range(len(aa) - 1):
            now = aa[i] + aa[i + 1]
            if now < mn:
                mn = now
                mi = i
        aa = aa[:mi] + [mn] + aa[mi + 2:]
        ans+=mn
    print(ans)

main()


### FIXED CODE ###

def f(n, a):
    inf = float("inf")
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
        s = a[i]
        dpi = dp[i]
        for j in range(i + 1, n):
            mn = inf
            s += a[j]
            for d in range(i, j):
                k = dpi[d] + dp[d + 1][j]
                if k < mn:
                    mn = k
            dpi[j] = mn + s
    return dp[0][-1]


n = int(input())
a = tuple(map(int, input().split()))
print(f(n, a))
### BUGGY CODE ###

nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[list(map(int, input().split())) for i in range(Q)]
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools as ite
case=list(ite.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        a=ablist[i][0]
        b=ablist[i][1]
        c=ablist[i][2]
        d=ablist[i][3]
        aa=nowcase[a-1]
        ab=nowcase[b-1]
        if ab-aa==c:
            sumd+=d
    sumlist.append(sumd)
print(max(sumlist))


### FIXED CODE ###

nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[]
for i in range(Q):
    tp=tuple(map(int, input().split()))
    ablist.append(tp)
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools
case=list(itertools.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        if nowcase[ablist[i][1]-1]-nowcase[ablist[i][0]-1]==ablist[i][2]:
            sumd+=ablist[i][3]
    sumlist.append(sumd)
print(max(sumlist))
### BUGGY CODE ###

MAX_LIMIT = 1e30
H, N = list(map(int, input().split()))
A, B = [], []
for _ in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)  # HP
    B.append(b)  # power

# dp[i] means minimum power used to reduce HP i
dp = [MAX_LIMIT] * (H + max(A))
dp[0] = 0

for i in range(1, H + max(A)):
    cands = []
    for a, b in zip(A, B):
        if i - a >= 0:
            cands.append(b + dp[i - a])
    if len(cands) == 0:
        dp[i] = MAX_LIMIT  # we cannot directly reach this point
    else:
        dp[i] = min(cands)

# print(dp)
print(min(dp[H:]))


### FIXED CODE ###

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
dp =[0]*(h+max(a for a,b in ab))
for i in range(1, h+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)
print(dp[h])
### BUGGY CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
# a <= b <= c

for b in range(1,N-1):
  for c in range(b+1,N):
    # search min(c) with a + b > c <=> a > c - b
    idx = bisect.bisect_left(L[:b],L[c]-L[b]+1)
    #print(L[b],L[c],idx)
    ans += max(b-idx,0) if idx >= 0 else 0 
    #print(idx, ans)
#print(L)
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
# a <= b <= c

for b in range(1,N-1):
  for c in range(b+1,N):
    # search min(c) with a + b > c <=> a > c - b
    idx = bisect.bisect_left(L[:b],L[c]-L[b]+1)
    #print(L[b],L[c],idx)
    ans += max(b-idx,0) if idx >= 0 else 0 
    #print(idx, ans)
#print(L)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

def solve(ab, hp, memo):
  if hp <= 0:
    return 0
  else:
    ans = 10**10
    if memo[hp] < 0:
      for attack, cost in ab:
        ans = min(ans, solve(ab, hp-attack, memo)+cost)
      memo[hp] = ans
    return memo[hp]

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [-1]*(H+1)
i = 0
while i <= H:
  solve(AB, i, memo)
  i += 1
print(memo[H])

### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
memo = [10**10]*(H+1)
memo[0] = 0
i = 0
while i <= H:
  for a, b in AB:
    memo[i] = min(memo[i], b+memo[max(0, i-a)])
  i += 1
print(memo[H])
### BUGGY CODE ###

import sys
n = int(input())
ans=0
for i in range(10):
    for j in range(10):
        a = 0
        b = 0
        #print(i,j)
        for k in range(1,n+1):
            if str(k)[0] == str(i) and str(k)[-1] == str(j):
                #sys.stdout.write(str(k)+",")
                a+=1
            if str(k)[0] == str(j) and str(k)[-1] == str(i):
                b+=1
                #print(k)
        ans+=a*b
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

c = [[0] * 10 for _ in range(10)]

for i in range(1,n + 1):
    c[int(str(i)[0])][int(str(i)[-1])]+=1

for i in range(10):
    for j in range(10):
        ans+=c[i][j] * c[j][i]
print(ans)
### BUGGY CODE ###

r,g,b,n = map(int, input().split())
count = 0
for i in range(1+n//r):
    for j in range(1+n//g):
        rest = n - i*r - g*j
        if rest >= 0 and rest%b == 0:
            count += 1
print(count)

### FIXED CODE ###

r,g,b,n = map(int, input().split())
count = 0
c0,c1,c2 = sorted([r,g,b])
for i in range(1+n//c2):
    rest1 = n - i*c2
    if rest1 < 0:
        break
    for j in range(1+rest1//c1):
        rest = n - i*c2 - j*c1
        if rest <0:
            break
        elif rest%c0 == 0:
            count += 1
print(count)
### BUGGY CODE ###

n = int(input())
ints = [0 for i in range(n)]

k = 1
summed = 0

for i in range(1, n + 1):
    if i != 1:
        while k * i <= n:
            ints[k * i - 1] += 1
            k += 1
        k = 1
    summed += (ints[i-1]+1) * i

print(summed)


### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1, n + 1):
    ans += i * (n // i) * (n // i + 1) // 2

print(ans)
### BUGGY CODE ###

import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r:, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

for p, q in pq:
    ans = np.sum(RcntL[q, p:q+1])
    print(ans)


### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

RcntL = np.cumsum(RcntL, axis=0)
RcntL = np.cumsum(RcntL, axis=1)

for p, q in pq:
    ans = RcntL[q, q] - RcntL[q, p - 1]
    print(ans)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())

    boats = []
    islands = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands.append(max(boat))

        boats.append(boat)

    for boat in boats:
        if boat[0] in islands:
            if boat[1] == n:
                print("POSSIBLE")
                return

        elif boat[1] in islands:
            if boat[0] == n:
                print("POSSIBLE")
                return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())

    islands_to_1 = [0 for _ in range(n+1)]
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1[boat[1]] = 1

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_n in islands_to_n:
        if islands_to_1[island_to_n] == 1:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


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

#
# abc049 c
#
s = input()
words = ['dream', 'dreamer', 'erase', 'eraser']

flag = 0
while len(s) > 0:
    for w in words:
        if s[-1 * len(w):] == w:
            s = s.replace(w, "").rstrip()
            flag = 1
            break
    if flag == 0:
        print("NO")
        exit()

print("YES")


### FIXED CODE ###

#
# abc049 c
#
s = input()
words = ['dream', 'dreamer', 'erase', 'eraser']

s = s[::-1]
while len(s) > 0:
    flag = 0
    for w in words:
        w = w[::-1]
        if s[0:len(w)] == w:
            s = s[len(w)::]
            # s = s.replace(w, "").lstrip()
            flag = 1
            break
    if flag == 0:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict((int))
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

### FIXED CODE ###

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)
### BUGGY CODE ###

import collections
a=int(input())
b=list(map(int,input().split()))

c=collections.Counter(b)
n,m=zip(*c.most_common())
m=list(m)
n=list(n)
q=0
for i in range(len(m)):
    t=(m[i]*(m[i]-1))//2
    q+=t

for i in range(a):
    w=m[n.index(b[i])]-1
    print(q-w)


### FIXED CODE ###

import collections
a=int(input())
b=list(map(int,input().split()))

c=collections.Counter(b)

n,m=zip(*c.most_common())
n,m=list(n),list(m)
result=0
for i in range(len(m)):
    result+=(m[i]*(m[i]-1))//2

for i in b:
    print(result-c[i]+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1 << 100
    NN = 2 * N + 6
    LN = NN.bit_length()
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    h = [0] * NN
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        Q = []
        heappush(Q, s)
        while len(Q):
            x = heappop(Q)
            d, v = (x>>LN), x % (1<<LN)
            if dist[v] < d: continue
            for i, (w, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[w] > dist[v] + c + h[v] - h[w]:
                    dist[w] = dist[v] + c + h[v] - h[w]
                    prevv[w] = v
                    preve[w] = i
                    heappush(Q, (dist[w] << LN) + w)
        if dist[t] == INF:
            return -1
        h = [0] * NN
        for v in range(N):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
N = int(input())
su = 0
inf = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + inf))
    E.append((i, 2*N+1, cnt, x - y + inf))
    E.append((i, 2*N+2, cnt, - x + y + inf))
    E.append((i, 2*N+3, cnt, - x - y + inf))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + inf))
    E.append((2*N+1, i+N, cnt, - x + y + inf))
    E.append((2*N+2, i+N, cnt, x - y + inf))
    E.append((2*N+3, i+N, cnt, x + y + inf))

print(su * inf * 2 - min_cost_flow_dijkstra(E, 2*N+4, 2*N+5, su))

### FIXED CODE ###

from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))
### BUGGY CODE ###

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

res = 0

for i in range(N-1):
    for j in range(i+1, N):
        res += (A[i] * A[j]) % (10 ** 9 + 7)
        res = res % (10 ** 9 + 7)
print(res)

### FIXED CODE ###

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

mod = 10 ** 9 + 7
ans = 0

A_sum = [A[0] for i in range(N)]
for i in range(1, N):
    A_sum[i] = A_sum[i-1] + A[i]

for i in range(1, N):
    ans += A[i] * A_sum[i-1]
    ans %= mod

print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

print(ans)
### BUGGY CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

g = [[False] * W for _ in range(H)]

for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    g[Th - 1][Tw - 1] = True

ans = max(h) + max(w)

index_h = [n for n, v in enumerate(h) if v == max(h)]
index_w = [n for n, v in enumerate(w) if v == max(w)]

sub = 1
for ih in index_h:
    for iv in index_w:
        if g[ih][iv] is False:
            sub = 0
            break
    else:
        continue
    break

ans -= sub
print(ans)


### FIXED CODE ###

import sys

H, W, M = map(int, sys.stdin.readline().strip().split())

h = [0] * H
w = [0] * W

# g = [[False] * W for _ in range(H)]
S = set()
for _ in range(M):
    Th, Tw = map(int, sys.stdin.readline().strip().split())

    h[Th - 1] += 1
    w[Tw - 1] += 1

    # g[Th - 1][Tw - 1] = True
    S.add((Th - 1, Tw - 1))

max_h = max(h)
max_w = max(w)
ans = max_h + max_w

index_h = [n for n, v in enumerate(h) if v == max_h]
index_w = [n for n, v in enumerate(w) if v == max_w]

sub = 1
# for ih in index_h:
#     for iv in index_w:
#         if g[ih][iv] is False:
#             sub = 0
#             break
#     else:
#         continue
#     break
# ans -= sub
# print(ans)


for ih in index_h:
    for iv in index_w:
        if not (ih, iv) in S:
            print(ans)
            exit()
print(ans - 1)