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

import math
import sys

n, m = map(int, input().split())
a_list = [None] * (m + 2)
a_list[0] = -1
for i in range(m):
    a_list[i+1] = int(input())
a_list[-1] = n + 1

fact_memo = dict()
def fact(n):
    if n in fact_memo.keys():
        return fact_memo[n]
    f = math.factorial(n)
    fact_memo[n] = f
    return f

memo = dict()
ans = 1
cur = a_list[0]
for a in a_list[1:]:
    sub = a - cur - 2
    cur = a
    if sub <= 1:
        if sub == -1:
            print(0)
            sys.exit()
        continue
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = sum(fact(sub - j) // fact(j) // fact(sub - j*2) for j in range(sub // 2 + 1))
    memo[sub] = count
    ans *= count
print(ans % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline

N, M = map(int, readline().split())
ans = [0] * (N + 2)
ans[0] = 1
for _ in range(M):
    a = int(readline())
    ans[a] = -1

for i in range(1, N + 1):
    if ans[i] == -1:
        continue
    a1 = max(ans[i - 2], 0)
    a2 = max(ans[i - 1], 0)
    ans[i] = a1 + a2

print(ans[N] % (10 ** 9 + 7))
### BUGGY CODE ###

N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = [[0 for _ in range(S + 1)] for _ in range(N)]
count3[0][0] = 2
count3[0][numbers[0]] = 1
count2 = [[0 for _ in range(S + 1)] for _ in range(N)]
count2[0][0] = 1
count2[0][numbers[0]] = 1

for i in range(1, N):
  for j in range(S + 1):
    if (count3[i - 1][j] > 0):
      count3[i][j + numbers[i]] += count3[i - 1][j]
      count3[i][j + numbers[i]] %= M
      count3[i][j] += 2 * count3[i - 1][j]
      count3[i][j] %= M
      count2[i][j + numbers[i]] += count2[i - 1][j]
      count2[i][j + numbers[i]] %= M
      count2[i][j] += count2[i - 1][j]
      count2[i][j] %= M

count_invalid = 0
for i in range(S):
  if (i > S / 2):
    count_invalid += count3[N - 1][i] - 2 * count2[N - 1][i]
    count_invalid %= M
if (S % 2 == 0):
  count_invalid += count3[N - 1][S // 2] - 2 * count2[N - 1][S // 2]
  count_invalid %= M

print((count_all - 3 * count_invalid) % M)


### FIXED CODE ###

import numpy as np

N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = np.zeros((N, S + 1), dtype=np.int64)
count3[0, 0] = 2
count3[0, numbers[0]] = 1
count2 = np.zeros((N, S + 1), dtype=np.int64)
count2[0, 0] = 1
count2[0, numbers[0]] = 1

for i in range(1, N):
    count3[i, numbers[i]:] += count3[i - 1, :-numbers[i]]
    count3[i, :] += 2 * count3[i - 1, :]
    count3[i, :] %= M
    count2[i, numbers[i]:] += count2[i - 1, :-numbers[i]]
    count2[i, :] += count2[i - 1, :]
    count2[i, :] %= M

invalid_from = S // 2 + 1
if (S % 2 == 0):
  invalid_from = S // 2
count_invalid = np.sum(count3[N - 1, invalid_from:-1]) - 2 * np.sum(count2[N - 1, invalid_from:-1])
count_invalid %= M

print((count_all - 3 * count_invalid) % M)
### BUGGY CODE ###

from collections import deque
import numpy as np
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[0]*n
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
for i in range(k):
  a,b=map(int,input().split())
  block[a-1].append(b-1)
  block[b-1].append(a-1)
for i in range(n):#スタートの選び方
    u=[0]*n
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        u[x]=1
        for j in link[x]:
            if u[j]==1:
              continue
            elif j in q:
              continue
            else:q.append(j)
    s.append(u)
    ans[i]=sum(u)-1
for i in range(n):
  for j in link[i]:
    if s[i][j]==1:
      ans[i]-=1
  for k in block[i]:
    if s[i][k]==1:
      ans[k]-=1
print(*ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
      self.n=n
      self.root=[-1]*(n+1)
      self.rank=[0]*(n+1)
      
    def find(self,x):
      if self.root[x]<0:
        return x
      else:
        self.root[x]=self.find(self.root[x])
        return self.root[x]
    
    def unite(self,x,y):
      x=self.find(x)
      y=self.find(y)
      if x==y:
        return 0
      elif self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      else:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
          
    def Same(self,x,y):
      return self.find(x)==self.find(y)
    
    def size(self,x):
      return -self.root[self.find(x)]
import sys
input=sys.stdin.buffer.readline
n,m,k=map(int,input().split())
link=UnionFind(n)
f=[0]*n
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    link.unite(a,b)
    f[a]+=1
    f[b]+=1
for _ in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
for i in range(n):
  ret=link.size(i)-f[i]-1
  for j in block[i]:
    if link.Same(i,j):
      ret-=1
  ans.append(ret)
print(*ans)
### BUGGY CODE ###

n,W=map(int,input().split())
wt=[]
value=[]
for i in range(n):
    x,y=map(int,input().split())
    value.append(y)
    wt.append(x)
dp = [0] * (W + 1)
for i in range(n):
    for j in range(W, wt[i]-1, -1):
        dp[j] = max(dp[j], value[i] + dp[j - wt[i]])
print(dp[W])

### FIXED CODE ###

import numba as nb
import sys
import numpy as np
@nb.njit
def solve(w,weight,value):
    total=w
    dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
    for i in range(l):
        for w in range(total+1):
            if weight[i]<=w:
                dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[l-1][total])
n,w=map(int,sys.stdin.readline().split())
weight=[0]*n
value=[0]*n
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight[i]=x
    value[i]=y
l=len(weight)
solve(w,weight,value)
### BUGGY CODE ###

def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]

best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

# print(best)
X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                
    
print(X[N])


### FIXED CODE ###

def intlog10(n):
    if n <= 0:
        return -1
    i = 0
    while 10**i <= n:
        i += 1
    return i-1

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
    
L = [2, 5, 5, 4, 5, 6, 3, 7, 6]
B = [[A[i], L[A[i]-1]] for i in range(M)]



best = sorted(B, key = lambda x: x[1]*10-x[0])[0]

adj = 0
if N > 500:
    adj = (N - 500)//best[1]
    N -= best[1] * adj

X = [0] + [-10**9] * N
bpre = -1
ll = 1
for i in range(1, N+1):
    if i > 50 and i < N-50:
        X[i] = X[i-best[1]]*10 + best[0]
    else:
        for b in B:
            if b[1] <= i:
                if X[i-b[1]] == 0:
                    if b[0] > X[i]:
                        X[i] = b[0]
                        bpre = b
                        ll = 0
                else:
                    if X[i-b[1]]*10 + b[0] < X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])):
                        lll = 1

                    if max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]]))) > X[i]:
                        X[i] = max(X[i-b[1]]*10 + b[0], X[i-b[1]] + b[0] * (10**intlog10(X[i-b[1]])))
                        ll = lll
                        bpre = b
                

ans = str(X[N])
if adj > 0:
    ans = ans[:50] + str(best[0]) * adj + ans[50:]

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

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

import itertools
AB = [a + b for a, b in itertools.product(A,B)]
ABC = [ab + c for ab, c in itertools.product(AB,C)]
ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

import itertools
AB = [a + b for a, b in itertools.product(A,B)]
AB.sort(reverse=True)
ABC = [ab + c for ab, c in itertools.product(AB[:3000],C)]
ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

n, W = map(int, input().split())
w, v = [], []

for i in range(n):
    temp1, temp2 = map(int, input().split())
    w.append(temp1)
    v.append(temp2)

#print(w, v)
#dp[i] = max(dp[i-1], dp[i]) + dp[i-2]

dp = [[None for i in range(W+1)] for j in range(n+1)]
#dp[0][0] = 0

#print(dp)

def solve(total, i):
    if dp[i][total] is not None:
        return dp[i][total]

    if i > n-1:
        return 0

    weight, val = w[i], v[i]
    if total + weight <= W:
        chose = val + solve(total + weight, i+1)
        unchose = solve(total, i+1)
        dp[i][total] = max(chose, unchose)
        return dp[i][total]
    else:
        dp[i][total] = solve(total, i+1)
        return dp[i][total]


print(solve(0, 0))

### FIXED CODE ###

n, W = map(int, input().split())
w = [0]*(n+1)
v = [0]*(n+1)

#dp = [[None for i in range(W+1)] for j in range(n+1)]
dp = [[0 for i in range(W+1)] for j in range(n+1)]

for i in range(n):
    w[i], v[i] = map(int, input().split())

def knap(i, j):
    if dp[i][j] is not None:
        return dp[i][j]

    res = 0

    if i == n:
       	res = 0
    elif j < w[i]:
        res = knap(i+1, j)
    else:
        res = max(knap(i+1, j), knap(i+1, j-w[i]) + v[i])

    dp[i][j] = res
    return dp[i][j]

for i in reversed(range(n)):
    for j in range(W+1):
#        res = 0
        # if i == n-1:
        #     res = 0
        if j < w[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i])

#print(knap(0, W))
print(dp[0][W])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    ans = 0
    for i in range(N-1):
        for j in range(i, N):
            for k in range(j, N):
                if (S[i] != S[j] and S[j] != S[k] and S[i] != S[k]) and (j - i != k - j):
                    ans += 1
    print(ans)

main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    ans = 0
    r, g, b = [0 for _ in range(N+1)], [0 for _ in range(N+1)], [0 for _ in range(N+1)]
    for i in range(N):
        r[i+1], g[i+1], b[i+1] = r[i], g[i], b[i]
        if S[i] == "R":
            r[i+1] += 1
        elif S[i] == "G":
            g[i+1] += 1
        else:
            b[i+1] += 1
    
    for i in range(1, N-1):
        if S[i] == "R":
            ans += g[i] * (b[N] - b[i+1]) + b[i] * (g[N] - g[i+1])
            for j in range(1, min(i, N-i-1)+1):
                if {S[i-j], S[i+j]} == {"G", "B"}:
                    ans -= 1
        
        elif S[i] == "G":
            ans += r[i] * (b[N] - b[i+1]) + b[i] * (r[N] - r[i+1])
            for j in range(1, min(i, N-i-1)+1):
                if {S[i-j], S[i+j]} == {"R", "B"}:
                    ans -= 1
        elif S[i] == "B":
            ans += g[i] * (r[N] - r[i+1]) + r[i] * (g[N] - g[i+1])
            for j in range(1, min(i, N-i-1)+1):
                if {S[i-j], S[i+j]} == {"G", "R"}:
                    ans -= 1
    print(ans)

main()
### BUGGY CODE ###

n, m, k = map(int, input().split())
MOD = 998244353

def fn(n, m):
  return (m*pow(m-1, n-1, MOD))%MOD

def nCr(n, r):
    fac = 1
    finv = 1
    for i in range(r):
        fac *= n-i
        fac %= MOD
        finv *= i+1
        finv %= MOD
    return fac * pow(finv, MOD-2, MOD) % MOD

ans = fn(n, m)
for i in range(1, k+1):
  ans += nCr(n-1,i)*fn(n-i, m)
  ans %= MOD
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353

def fn(n, m):
  return (m*pow(m-1, n-1, MOD))%MOD

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, n):
  fact.append((fact[-1]*i) % MOD)
  inv.append((-inv[MOD % i] * (MOD // i) % MOD))
  factinv.append((factinv[-1] * inv[-1]) % MOD)
  
def nCr(n, r):
    return fact[n] * factinv[r] * factinv[n-r] % MOD

ans = fn(n, m)
for i in range(1, k+1):
  ans += nCr(n-1, i)*fn(n-i, m)
  ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
for i in range(N-1):
  for j in range(N-i-1):
    sums+=(As[i]*As[i+j+1])%moder
print(sums%moder)

### FIXED CODE ###

N = int(input())
As = list(map(int,input().split()))
sums = 0
moder = 1000000007
s=[0 for i in range(N-1)]
s[-1] = As[-1]
for i in range(N-2):
  s[-(i+2)] = s[-(i+1)]+As[-(i+2)]

for i in range(N-1):
  sums+= (As[i]*s[i])%moder
print(sums%moder)
### BUGGY CODE ###

import numpy as np
n,m=map(int,input().split())
r=np.array([list(map(int,input().split())) for _ in range(m)])
start=np.array([1])
done=np.array([1])
ans=np.array([-1]*n)

while len(done)!=n:
    start_tmp=np.array([])
    for st in start:
        r_st = r[np.any(r==st, axis=1)].flatten()
        r_gl = np.delete(r_st, np.where(r_st == st))
        r_gl = np.setdiff1d(r_gl, done)
        
        start_tmp=np.unique(np.append(start_tmp, r_gl))
        done=np.unique(np.append(done, r_gl))
        #print(r_gl)
        ans[r_gl-1] = st
        
    start = start_tmp
    #print(ans)
    #print(start, done)
    
print('Yes')
print('\n'.join(map(str, ans[1:])))

### FIXED CODE ###

print('Yes')

from collections import deque  

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

ans = [-1] * (n+1)
ans[0] = 0
ans[1] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if ans[i] != -1:
            continue
        ans[i] = v
        d.append(i)

print(*ans[2:], sep="\n")
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
icount = 0
for i in range(n):
    pi = li[i]
    for i in range(i + 1):
        if pi > li[i]:
            break
    if pi <= li[i]:
        icount += 1
print(icount)


### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
count = 1
min_p = p[0]
for i in range(n):
    if min_p > p[i]:
        count += 1
        min_p = p[i]
print(count)
### BUGGY CODE ###

import heapq
n=int(input())
a=list(map(int,input().split()))
ans=[0 for i in range(n+1)]
ans[0]=sum(a[:n])
b=a[:n]
heapq.heapify(b)
for i in range(n):
  c=heapq.heappop(b)
  if c>a[n+i]:
    heapq.heappush(b,c)
    ans[i+1]=sum(b)
  else:
    heapq.heappush(b,a[n+i])
    ans[i+1]=sum(b)
b=a[2*n:]
for i in range(n):
  b[i]=-b[i]
heapq.heapify(b)
ans[n]+=sum(b)
for i in range(n-1,-1,-1):
  c=heapq.heappop(b)
  if c>-a[n+i]:
    heapq.heappush(b,c)
    ans[i]+=sum(b)
  else:
    heapq.heappush(b,-a[n+i])
    ans[i]+=sum(b)
print(max(ans))

### FIXED CODE ###

import heapq
n=int(input())
a=list(map(int,input().split()))
ans=[0 for i in range(n+1)]
ans[0]=sum(a[:n])
b=a[:n]
heapq.heapify(b)
sb=sum(b)
for i in range(n):
  sb+=a[n+i]
  c=heapq.heappushpop(b,a[n+i])
  sb-=c
  ans[i+1]=sb
b=a[2*n:]
for i in range(n):
  b[i]=-b[i]
heapq.heapify(b)
ans[n]+=sum(b)
sb=sum(b)
for i in range(n-1,-1,-1):
  sb-=a[n+i]
  c=heapq.heappushpop(b,-a[n+i])
  sb-=c
  ans[i]+=sb
print(max(ans))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())
F = [list(input()) for _ in range(H)]

move = (-1, 1)
count = []

def dfs(i, j, seen):
    seen.add((i, j))
    if F[i][j] == '#':
        next = '.'
    else:
        next = '#'

    for m in move:
        if 0 <= i+m < H and F[i+m][j] == next and (i+m, j) not in seen:
            seen.add((i+m, j))
            if F[i][j] == '#':
                count.append((i+m, j))

            dfs(i+m, j, seen)
        if 0 <= j+m < W and F[i][j+m] == next and (i, j+m) not in seen:
            seen.add((i, j+m))
            if F[i][j] == '#':
                count.append((i, j+m))
            dfs(i, j+m, seen)

for i in range(H):
    for j in range(W):
        if F[i][j] == '#':
            dfs(i, j, set())

print(len(count))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

H, W = map(int, input().split())
F = [list(input()) for _ in range(H)]

move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
seen = [[0] * W for _ in range(H)]

# Fの点を頂点とするグラフを考える。グラフの連結成分に'#'がbコ, '.'がwコある場合、
# b*wが条件を満たす

def dfs(sy, sx):
    seen[sy][sx] = 1
    b, w = 1, 0
    
    for dy, dx in move:
      ny = sy + dy
      nx = sx + dx
      if 0 <= ny < H and 0 <= nx < W and F[ny][nx] != F[sy][sx] and not seen[ny][nx]:
        p = dfs(ny, nx)
        b += p[1]  # 逆にしている
        w += p[0]  # 天才か？
    return (b, w)
        
count = 0
for i in range(H):
    for j in range(W):
        if not seen[i][j]:
            b, w = dfs(i, j)
            count += b * w

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

from collections import Counter
S = input()
S = S[::-1]
# 1桁のmod2019, 2桁の2019, ...
# 0桁のmod2019=0と定めると都合が良い
l = [0]
num = 0
for i in range(len(S)):
    num += int(S[i]) * (10**i)
    l.append(num % 2019)
# print(l)
ans = 0
c = Counter(l)
for v in c.values():
    ans += v*(v-1)//2
print(ans)


### FIXED CODE ###

from collections import Counter

# forを逆から回して下から素直にmodを取るとTLEだった
# 累積和的な計算で高速化、やりやすくするためにreverse
S = input()[::-1]
# ex. 1817181712114 → 4112171817181
# print(S)

# 0桁目までのMODを0とすることで、
# 1桁目を含む数が2019の倍数の時に都合が良くなる
X = [0]

# 4,14,114,2114,12114,...のmod2019を計算

for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, 2019)) % 2019)
# print(X)


C = Counter(X)
# print(C)

ans = 0
# Xが同じになったところを2つ選べば題意を満たす
# v_C_2の計算
for v in C.values():
    ans += v * (v - 1) // 2

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

from bisect import bisect_left
N, M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
for i in range(M):
  A[-1]=A[-1]//2
  idx=bisect_left(A, A[-1])
  A.insert(idx, A[-1])
  A.pop()
print(sum(A))

### FIXED CODE ###

import heapq
N, M=map(int, input().split())
A=list(map(int, input().split()))
A=list(map(lambda x: -x, A))
heapq.heapify(A)
for i in range(M):
  heapq.heappush(A, (heapq.heappop(A)+1)//2)
print(-sum(A))
### BUGGY CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def get_score(i, j):
    return i+j-2

n = int(input())
prime_list = prime_factorize(n)
# print(prime_list)

ans = 1e13
for i in range(2 ** len(prime_list)):
    total = 0
    a = 1
    b = 1
    for j in range(len(prime_list)):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            a *= prime_list[j]
        else:
            b *= prime_list[j]
    score = get_score(a, b)
    if ans > score:
        ans = score
print(ans)


### FIXED CODE ###

n = int(input())
ans = 1e14
for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        score = i + n//i -2
        if ans > score:
            ans = score
print(ans)
### BUGGY CODE ###

import copy
N, M, K = map(int, input().split())
tomodachi  = [ [i] for i in range(N+1)]
for _ in range(M):
  a, b  = map(int, input().split())
  tomodachi[a].append(b)
  tomodachi[b].append(a)
dupli = copy.deepcopy(tomodachi)

for n in range(1, N+1):
  kouho = set()
  for friend in tomodachi[n]:
    if friend == n:
      continue
    else:
      kouho.add(friend)
  while kouho:
    f = kouho.pop()
    for g in tomodachi[f]:
      if g in tomodachi[n]:
        continue
      else:
        kouho.add(g)
        tomodachi[n].append(g)


for _ in range(K):
  c, d  = map(int, input().split())
  if c in tomodachi[d]:
    tomodachi[d].remove(c)
    tomodachi[c].remove(d)

ans = [ len(t)-len(s) for s, t in zip(dupli[1:], tomodachi[1:]) ]
print(' '.join(list(str(i) for i in ans)))

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
      
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if uf.same(c, d):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
M=max(A)

for i in range(N):
    if M>A[i]:
        print(M)
    elif M==A[i]:
        A[i]=0
        print(max(A))
        A[i]=M

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
M=sorted(A)

for i in range(N):
    if M[N-1]>A[i]:
        print(M[N-1])
    elif M[N-1]==A[i]:
        print(M[N-2])
### BUGGY CODE ###

s = input()
sc = s[::-1]
n = int(input())
l = [list(input().split()) for i in range(n)]

last = 1

for i in range(n):
    if l[i][0] == '1':
        last = last * -1
    else:
        if l[i][1] == '1' and last > 0:
            s = l[i][2] + s
            sc += l[i][2]
        elif l[i][1] == '2' and last > 0:
            s += l[i][2]
            sc = l[i][2] + sc
        elif l[i][1] == '1' and last < 0:
            s += l[i][2]
            sc = l[i][2] + sc
        else:
            s = l[i][2] + s
            sc += l[i][2]

if last > 0:
    print(s)
else:
    print(sc)

### FIXED CODE ###

import copy
from collections import deque
s = deque(input())
sc = copy.deepcopy(s) 
sc.reverse()
n = int(input())
l = [list(input().split()) for i in range(n)]

for i in range(n):
    if l[i][0] == '1':
        save = s
        s = sc
        sc = save
    elif l[i][1] == '1':
        s.appendleft(l[i][2])
        sc.append(l[i][2])
        #s = l[i][2] + s
        #sc += l[i][2]
    else:
        s.append(l[i][2])
        sc.appendleft(l[i][2])
        #s += l[i][2]
        #sc = l[i][2] + sc

print(''.join(s))
### BUGGY CODE ###

import math

L, R = map(int, input().split())

ans = 2019

for i, j in zip(range(2019), range(L, R)):
    for k in range(j+1, R+1):
        lr_mod = (j * k) % 2019
        if lr_mod < ans:
            ans = lr_mod

print(ans)

### FIXED CODE ###

import math

L, R = map(int, input().split())

ans = 2019

for i, j in zip(range(2019), range(L, R)):
    for k in range(j+1, min(L + 2019*2, R + 1)):
        lr_mod = (j * k) % 2019
        if lr_mod < ans:
            ans = lr_mod
        if ans==0:break
    if ans==0:break

print(ans)