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

from heapq import heappop, heappush
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]

D = []
for a in A:
    heappush(D, a)
for b, c in BC:
    for _ in range(b):
        if c > D[0]:
            heappush(D, max(heappop(D), c))
print(sum(D))

### FIXED CODE ###

from heapq import heapify, heappushpop
from operator import itemgetter
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
heapify(A)
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]
BC.sort(key=itemgetter(1), reverse=True)

for b, c in BC:
    for _ in range(b):
        if c > A[0]:
            _ = heappushpop(A, c)
        else:
            break
print(sum(A))
### BUGGY CODE ###

n = int(input())
c = 0
l = [''.join(sorted(input())) for _ in range(n)]
c = 0
for i in range(n):
    for j in range(i+1, n):
        if l[i] == l[j]:
            c += 1
print(c)

### FIXED CODE ###

n = int(input())
c = 0
d = {}
for _ in range(n):
    i = ''.join(sorted(input()))
    if i in d:
        c += d[i]
        d[i] += 1
    else:
        d[i] = 1
print(c)
### BUGGY CODE ###

N, M = map( int, input().split() )
a = list( map( int, input().split() ) )
 
d = []
for i in range( M ):
  b, c = map( int, input().split() )
  d += [ c ] * b
d.sort()
a += d[-N:]
a.sort()
print(sum(a[-N:]))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

ans = 0
Sum = 0
A.sort(reverse=True)
B.sort(reverse=True)
#A_b:a以上のBのパーツ数。ソートしているのでそのままBのindexと対応が付く
A_b = [sum(b > a for b in B) for a in A] 
B_c = [sum(c > b for c in C) for b in B]

ans = sum(sum(B_c[:x]) for x in A_b) 
#aはB[i](i<x)の上に乗せられる。
#B[i]を乗せられるCのパーツ数はリストB_cにまとめてある。
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

import bisect as bs
import numpy as np
A.sort()
C.sort()
#B_a:b未満のAのパーツ数、B_c:b超のCのパーツ数
B_a = np.array([bs.bisect_left(A,b) for b in B]) 
B_c = np.array([N-bs.bisect_right(C,b) for b in B])
ans = np.dot(B_a, B_c)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
x = 0
y = 0
for i in range(0, n):
    if x <= y:
        x += a.pop(0)
    else:
        y += a.pop(-1)
print(abs(x - y))

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
x = 0
y = 0
be = 0
af = -1
for i in range(0, n):
    if x <= y:
        x += a[be]
        be += 1
    else:
        y += a[af]
        af -= 1
print(abs(x - y))
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections

n = int(input())
# n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))

MOD = 10 ** 9 + 7

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

        # print(i, j, _)

print(sum % MOD)


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections

n = int(input())
# n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))

MOD = 10 ** 9 + 7

wa = 0
for i in range(1, n):
    wa += a[i]

# print('wa', wa)

ans = 0
j = 1
for i in range(n - 1):
    ttl = a[i] * wa
    ans += ttl

    wa -= a[j]
    j += 1

    # print('new wa', wa)

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

import sys
input = sys.stdin.readline
import random

D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]

sumC = sum(C)
def score(strategy):
    sat = 0
    last = [0]*26
    for i,ind in enumerate(strategy):
        last = [l+1 for l in last]
        last[ind] = 0
        sat -= sum((c*l for c,l in zip(C,last)))
        sat += S[i][ind]
    return sat

#first = [np.argmax(ds) for ds in S]
first = [i % 26 for i in range(D)]

ans = first
now_score = score(ans)

for i in range(5):
    for d in range(D):
        temp = ans[:]
        temp[d] = S[d].index(max(S[d]))
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for i in range(18):
    samples = [random.randint(0,25) for j in range(D)]
    for d in range(D):
        temp = ans[:]
        temp[d] = samples[d]
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for i in range(3):
    for d in range(D):
        temp = ans[:]
        temp[d] = S[d].index(max(S[d]))
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for a in ans:
    print(a+1)



### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

D = int(input())
C = np.array(list(map(int,input().split())),dtype=np.int)
S = np.array([list(map(int,input().split())) for i in range(D)],dtype=np.int)

sumC = sum(C)
def score(strategy):
    sat = 0
    last = np.zeros(26).astype(np.int)
    for i,ind in enumerate(strategy):
        last += 1
        last[ind] = 0
        sat -= np.sum(C * last)
        sat += S[i][ind]
    return sat

#first = [np.argmax(ds) for ds in S]
first = [i % 26 for i in range(D)]

ans = first
now_score = score(ans)

for i in range(1):
    samples = np.random.randint(0,26,size=D).tolist()
    for d in range(D):
        temp = ans[:]
        temp[d] = samples[d]
        if score(temp) > now_score:
            ans = temp

for a in ans:
    print(a+1)
### BUGGY CODE ###

import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
NoNeed = 0
count = 0
while Possible and count < N * (N-1) // 2:
    for c in Comb:
        a, i, j = A[c[0]][c[1]], c[0], c[1]
        count += 1
        MinDist = float("inf")
        for k in range(N):
            if k != i and k != j:
                MinDist = min(MinDist, A[i][k] + A[k][j])
        if MinDist < a:
            Possible = False
        elif MinDist == a:
            NoNeed += a
        

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)

else:
    print(-1)

### FIXED CODE ###

import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n = int(input())
cnt = 0
for i in range(n):
   cnt += i
print(cnt)

### FIXED CODE ###

n = int(input())
ans = n * (n-1) //2
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    a = int(input())
    A.append(a)
amax = max(A)
amaxcnt = A.count(amax)

for i in range(N):
    a0 = A.pop(0)
    if a0 == amax and amaxcnt == 1:
        print(max(A))
    else:
        print(amax)


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
amax = max(A)
amaxcnt = A.count(amax)

for i in range(N):
    ai = A[i]
    if ai == amax and amaxcnt == 1:
        A.pop(i)
        print(max(A))
        A.insert(i, 0)
    else:
        print(amax)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1,n):
    ans+=i
print(ans)

### FIXED CODE ###

n=int(input())
print(int((n-1)*n)//2)
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(1,N + 1):
    ans *=  i 
ans %= (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

N = int(input())

ans = 1
mod = 10**9 + 7

for i in range(1, N + 1):
    ans = (ans * i) % mod

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

N,Q = [int(i) for i in input().split()]
S = input()
q_list = []
for i in range(Q) :
    q_list.append([int(i) for i in input().split()])

# もちろんTLE。。。
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
#     find_index = 0
#     ac_count = 0
#     while(find_index != -1) :
#         find_index = search_str.find("AC",find_index)
#         if (find_index != -1) :
#             ac_count += 1
#             find_index += 1
#     print(ac_count)

for item in q_list :
    from_index = item[0]
    to_index = item[1]
    search_str = S[from_index-1:to_index]
    print(search_str.replace("AC","X").count("X"))
        


### FIXED CODE ###

N,Q = [int(i) for i in input().split()]
S = input()
q_list = []
for i in range(Q) :
    q_list.append([int(i) for i in input().split()])


## No.5
# n番目までに何回ACって出るか調べたらO(N)で済むのでは？
c = 0
ac_list = []
for i in range(len(S)) :
    # Cの位置を基準にする
    if (S[i] == "C" and i > 0 and S[i-1] == "A") :
        c += 1
        ac_list.append(c)
    else :
        ac_list.append(c)

for item in q_list :
    # XXXXA | C だったケースは除外するので、右端は-1する
    ac_count = ac_list[item[1]-1] - ac_list[item[0]-1]
    print(ac_count)



## No.4
# a_indexes = []
# # 下処理として、Aの場所だけ覚えておく
# for i in range(len(S)) :
#     if (S[i] == "A") :
#         a_indexes.append(i)

# # 幅に応じて、Aの次がCかどうかを判定する
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     # 次の文字がCであることを調べるので、toは1文字手前にする
#     target_indexes = [i for i in a_indexes if i >= from_index-1 and i < to_index-1]
#     ac_count = 0
#     for index in target_indexes :
#         if (S[index+1] == "C") :
#             ac_count += 1
    
#     print(ac_count)


## No.1  もちろんTLE。。。
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
#     find_index = 0
#     ac_count = 0
#     while(find_index != -1) :
#         find_index = search_str.find("AC",find_index)
#         if (find_index != -1) :
#             ac_count += 1
#             find_index += 1
#     print(ac_count)

## No.2,3
# for item in q_list :
#     from_index = item[0]
#     to_index = item[1]
#     search_str = S[from_index-1:to_index]
    # print(search_str.replace("AC","X").count("X"))
    # print(search_str.count("AC"))
### BUGGY CODE ###

n = int(input())
*arr, = map(int, input().split())
res = 1
for i in range(n):
    res *= arr[i]
print(res if res <= 10 ** 18 else - 1)


### FIXED CODE ###

n = int(input())
*arr, = map(int, input().split())
arr.sort()
res = 1
for i in range(n):
    res *= arr[i]
    if res > 10 ** 18:
        break
print(res if res <= 10 ** 18 else - 1)
### BUGGY CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

import bisect as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        left = abs(L[j] - L[k])
        L_slice = L[k:N]
        ite_right = bi.bisect_left(L_slice,right)
        ite_left = bi.bisect_left(L_slice,left)
        count = count + (ite_right - ite_left - 1)

print(count) 

### FIXED CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        ite_right = bi(L,right)
        count = count + (ite_right - k - 1)

print(count)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        break
    for j in range(i+1,n):
        if done[j] != 1:
            if li[j]==li[i]:
                done[i]=0
                done[j]=0
                dp[i]=0
                dp[j]=0
            elif li[j]%li[i]==0:
                done[j]=0
                dp[j]=0
 
print(sum(dp))

### FIXED CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

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

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print(-1)
            exit()

    memo=[-1 for i in range(0,n)]
    def dfs(num):
        if memo[num]!=-1:
            return memo[num]

        if not bool[num]:
            memo[num]=0
            return memo[num]
        else:
            ans=1+dfs((num+m)%n)
            memo[num]=ans
            return memo[num]

    answer=0
    for i in range(0,n):
        answer=max(answer,dfs(i))
    print(answer)
else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print(-1)
            break
    else:
        print(0)


### FIXED CODE ###

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print(-1)
            exit()

    ans=[[] for i in range(0,g)]
    for i in range(0,g):
        ans[i].append(bool[i])
        x=(i+m)%n
        while x!=i:
            ans[i].append(bool[x])
            x=(x+m)%n

    from itertools import groupby
    answer=0
    for i in range(0,g):
        a=groupby(ans[i])
        d=[]
        for key,group in a:
            g=len(list(group))
            d.append([key,g])
        if d:
            if d[0][0] and d[-1][0]:
                d[-1][1]+=d[0][1]
        for j in range(len(d)):
            if d[j][0]:
                answer=max(answer,d[j][1])
    print(answer)


else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print(-1)
            break
    else:
        print(0)
### BUGGY CODE ###

import numpy as np

def func(i,j,k):
    num = str(k)
    if int(num[0])==i and int(num[-1])==j:
        return True
    return False

n = int(input())
table = np.zeros((9,9))
for i in range(9):
    for j in range(9):
        for k in range(n):
            if func(i+1,j+1,k+1):
                table[i][j]+=1

ans = 0
for i in range(9):
    for j in range(9):
        ans += table[i][j]*table[j][i]
print(int(ans))

### FIXED CODE ###

import numpy as np

n = int(input())
table,ans = np.zeros((9,9)),0

for k in range(n):
    num = str(k+1)
    if int(num[0])!=0 and int(num[-1])!=0:
        table[int(num[0])-1][int(num[-1])-1]+=1

for i in range(9):
    for j in range(9):
        ans += table[i][j]*table[j][i]
print(int(ans))
### BUGGY CODE ###

import heapq
xs, ys, xt, yt = map(int, raw_input().split())
N = int(input())
C = [(xs, ys, 0), (xt, yt, 0)]
C += [tuple(map(int, raw_input().split())) for i in range(N)]

G = [[] for i in range(N+2)]
for i in range(N+2):
    for j in range(i+1, N+2):
        cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
        G[i].append((j, cost))
        G[j].append((i, cost))


def dijkstra(x):
    d = [float('inf')] * (N + 2)
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


dist = dijkstra(0)
print dist[1]


### FIXED CODE ###

import sys
import heapq
my_input = sys.stdin.readline

def main():
    xs, ys, xt, yt = map(int, my_input().split())
    N = int(my_input())
    C = [(xs, ys, 0), (xt, yt, 0)]
    C += [tuple(map(int, my_input().split())) for i in range(N)]

    G = [[] for i in range(N+2)]
    for i in range(N + 2):
        for j in range(i + 1, N + 2):
            cost = max(0, ((C[i][0] - C[j][0]) ** 2 + (C[i][1] - C[j][1]) ** 2) ** 0.5 - (C[i][2] + C[j][2]))
            G[i].append((j, cost))
            G[j].append((i, cost))


    def dijkstra(graph, start, inf=float('inf')):
        import heapq
        n = len(graph)
        distances = [inf] * n
        distances[start] = 0
        visited = [False] * n

        # 距離・頂点
        hq = [(0, start)]
        while hq:
            dist, fr = heapq.heappop(hq)
            if distances[fr] < dist:
                continue
            if fr == 1:
                return distances
            visited[fr] = True

            for to, cost in graph[fr]:
                new_dist = distances[fr] + cost
                if (visited[to]) or (distances[to] <= new_dist):
                    continue

                distances[to] = new_dist
                heapq.heappush(hq, (new_dist, to))

        return distances


    dist = dijkstra(G, 0)
    print(dist[1])


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

s = input()
t = input()
s_dup_lists = []
t_dup_lists = []

for i, (s1, t1) in enumerate(zip(s, t)):
    for j, (s2, t2) in enumerate(zip(s, t)):
        if (i != j) and (s1 == s2):
            s_dup_lists.append([i, j])
        if (i != j) and (t1 == t2):
            t_dup_lists.append([i, j])

if s_dup_lists == t_dup_lists:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
t = input()

s_dict = {}
t_dict = {}
s_drdp = sorted(set(s), key=s.index)
t_drdp = sorted(set(t), key=t.index)
for i, ss in enumerate(s_drdp):
    s_dict[ss] = i
for i, tt in enumerate(t_drdp):
    t_dict[tt] = i

import numpy as np

def s2vec(d, d_dict):
    return d_dict[d]

vecf = np.vectorize(s2vec)
if list(vecf(list(s), s_dict)) == list(vecf(list(t), t_dict)):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

(N, K) = map(lambda a: int(a), input().split())
A = list(map(lambda a: int(a), input().split()))

def proc():
    global A
    B = [0 for _ in range(N)]

    for i in range(0,N):
        f = max(0, i - A[i])
        t = min(N-1, i + A[i])
        #for j in range(max(0, f), min(N, t)+1):
        #    B[j] += 1
        B[f] += 1
        if t+1 < N:
            B[t+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    A = B

i = 0
while i in range(0, K):
    proc()
    if all(map(lambda a: a == N, A)):
        i = K
    i += 1

print(" ".join(map(lambda a: str(a), A)))

### FIXED CODE ###

import numpy as np
from numba import njit

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

@njit
def solve(N,K,A):
    for j in range(0, K):
        B = np.zeros(N, dtype=np.int64)

        for i in range(0,N):
            f = max(0, i - A[i])
            t = min(N-1, i + A[i])
            #for j in range(max(0, f), min(N, t)+1):
            #    B[j] += 1
            B[f] += 1
            if t+1 < N:
                B[t+1] -= 1
        A = np.cumsum(B)
        if np.all(A == N):
            return A
        i += 1
    return A
    

print(" ".join(map(str, solve(N,K,A))))
### BUGGY CODE ###

from collections import deque
N, M, K = map(int, input().split())
F = dict()
Block = dict()
for i in range(1, N+1):
    F[i] = []
    Block[i] = []

for _ in range(M):
    A, B = map(int, input().split())
    F[A].append(B)
    F[B].append(A)
for _ in range(K):
    C, D = map(int, input().split())
    Block[C].append(D)
    Block[D].append(C)

def dfs(i, F):
    cnt = 0
    visited = [False]*N
    visited[i-1] = True
    deq = deque(F[i])
    while deq:
        Q = deq.pop()
        if type(Q) == int:
            Q = [Q]
        for q in Q:
            if visited[q-1]:
                continue
            visited[q-1] = True
            if q not in F[i] and q not in Block[i]:
                cnt += 1
            deq += F[q]
            deq = list(set(deq))
    return cnt

for i in range(1, N+1):
    if i != N:
        print(dfs(i, F), end=' ')
    else:
        print(dfs(i, F))

### FIXED CODE ###

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

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)
 
    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        x = self.find(x)
        return -self.ps[x]

uf = UnionFind(N)
friends = [0]*(N+1)
chain = [0]*(N+1)


for _ in range(M):
    A, B = map(int, input().split())
    friends[A] += 1
    friends[B] += 1
    uf.union(A, B)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.same(C, D):
        friends[C] += 1
        friends[D] += 1

ans = []

for i in range(1, N+1):
    ans.append(uf.size(i) - friends[i] - 1)

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

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1
    
MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]

import itertools
X = list(itertools.product(h_list, w_list))

ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if (h[i],w[i]) in X:
        check += 1
        
if len(X)==check:
    ans -= 1
    
print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1

MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]


ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if counter_h[h[i]]==MAX_h and counter_w[w[i]]==MAX_w:
        check += 1

if len(h_list)*len(w_list)==check:
    ans -= 1

print(ans)