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

import queue

H, W = list(map(int, input().split()))
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S = [S[0] - 1, S[1] - 1]
G = [G[0] - 1, G[1] - 1]

maze = []
for i in range(H):
    maze.append(input())

MAX = 1000001
cost_list = [[MAX] * W for i in range(H)]


to_walk = queue.Queue()
to_warp = queue.Queue()


def walk(z):
    h, w = z
    cost = cost_list[h][w]
    to_warp.put([h, w])
    for [p, q] in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        a,b=h+p,w+q
        if (0 <= a < H) and (0 <= b < W):
            if maze[a][b] == "." and cost_list[a][b] > cost:
                cost_list[a][b] = cost
                to_walk.put([a,b])
                to_warp.put([a,b])


def warp(z):
    h, w = z
    cost = cost_list[h][w] + 1
    for [p, q] in [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, -1], [-1, 1], [-1, 2], [0, -2],
                   [0, 2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]:
        a,b=h+p,w+q
        if (0 <= a < H) and (0 <= b < W):
            if maze[a][b] == "." and cost_list[a][b] > cost:
                cost_list[a][b] = cost
                to_walk.put([a, b])


to_walk.put(S)
cost_list[S[0]][S[1]] = 0

while True:
    while not to_walk.empty():
        walk(to_walk.get())
    while not to_warp.empty():
        warp(to_warp.get())
    if to_walk.empty() and to_warp.empty():
        break

if cost_list[G[0]][G[1]] == MAX:
    print(-1)
else:
    print(cost_list[G[0]][G[1]])



### FIXED CODE ###

import queue
h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
s=[input() for _ in range(h)]
q=queue.deque([[sy-1,sx-1]])
q2=[[sy-1,sx-1]]
q3=[]
inf=10**7
dist=[[inf for _ in range(w)] for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
dist[sy-1][sx-1]=0

while q:
    y,x=q.pop()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==inf:
            dist[ny][nx]=min(dist[y][x],dist[ny][nx])
            q.append([ny,nx])
            q2.append([ny,nx])
    if not q:
        for y,x in q2:
            for dy in range(-2,3):
                for dx in range(-2,3):
                    ny,nx=y+dy,x+dx
                    if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==inf:
                        dist[ny][nx]=min(dist[y][x]+1,dist[ny][nx])
                        q.append([ny,nx])
                        q3.append([ny,nx])
        q2=q3
        q3=[]
print(dist[gy-1][gx-1] if dist[gy-1][gx-1]!=inf else -1)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 1
for a in A:
    ans *= a
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
ans = 1
if 0 in A:
    print(0)
    exit(0)
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        exit(0)
print(ans)
### BUGGY CODE ###

n = int(input())
sitigosan_list = [3, 5, 7]
count = 0

if n < 357:
    print(0)
    exit()

def make_753(num):
    b = str(num) + '3'
    c = str(num) + '5'
    d = str(num) + '7'
    sitigosan_list.append(int(b))
    sitigosan_list.append(int(c))
    sitigosan_list.append(int(d))


for i in sitigosan_list:
    make_753(i)
    if max(sitigosan_list) > n:
        break

for j in sitigosan_list:
    if '3' in str(j) and '5' in str(j) and '7' in str(j) and j <= n:
        count += 1

print(count)


### FIXED CODE ###

n = int(input())

sitigosan_list = [3, 5, 7]
count = 0

if n < 357:
    print(0)
    exit()

def make_753(num):
    global count
    b = str(num) + '3'
    c = str(num) + '5'
    d = str(num) + '7'
    if int(b) > n:
        return
    elif '3' in str(b) and '5' in str(b) and '7' in str(b):
        count += 1
        make_753(b)
    else:
        make_753(b)
    if int(c) > n:
        return
    elif '3' in str(c) and '5' in str(c) and '7' in str(c):
        count += 1
        make_753(c)
    else:
        make_753(c)
    if int(d) > n:
        return
    elif '3' in str(d) and '5' in str(d) and '7' in str(d):
        count += 1
        make_753(d)
    else:
        make_753(d)


make_753('')

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

S=str(input())
Q=int(input())
for i in range(Q):
	a=list(map(str,input().split()))
	if a[0]=="1":
		S=S[::-1]
	elif a[0]=="2":
		if a[1]=="1":
			S=a[2]+S
		elif a[1]=="2":
			S=S+a[2]
print(S)

### FIXED CODE ###

S=str(input())
Q=int(input())
count=0
M=''
U=''
for i in range(Q):
	a=list(map(str,input().split()))
	if a[0]=="1":
		count+=1
	elif a[0]=="2":
		if count%2==0:
			if a[1]=="1":
				M=a[2]+M
			elif a[1]=="2":
				U=U+a[2]
		elif count%2==1:
			if a[1]=="1":
				U=U+a[2][::-1]
			elif a[1]=="2":
				M=a[2][::-1]+M
S=M+S+U
if count%2==1:
	print(S[::-1])
else:
	print(S)
### BUGGY CODE ###

#!/usr/bin/env python3

import math

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

idl = []
idr = []

for i in range(m):
    a,b = list(map(int,input().split(" ")))
    idl.append(a)
    idr.append(b)

ans  = 0

for i in range(n):
    flg = 0
    for j in range(m):
        if idl[j] <= i+1 <= idr[j]:
            pass
        else:
            flg = 1
    if flg == 0:
        ans += 1
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import math

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

s = 0
t = 10**5+1
for i in range(m):
    a,b = list(map(int,input().split(" ")))
    if s < a:
        s = a
    if b < t:
        t = b
if t < s:
    print(0)
else:
    print(t-s+1)
### BUGGY CODE ###

import collections

def main():
    li = []
    ans = 0
    n,m = map(int,input().split())
    for _ in range(m):
        l,r = map(int, input().split())
        for i in range(l,r+1):
            li.append(i)
    c = collections.Counter(li)
    for i,v in c.items():
        if v >= m:
            ans += 1
    print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
    ll = []
    rl = []
    n,m = map(int,input().split())
    for _ in range(m):
        l,r = map(int, input().split())
        ll.append(l)
        rl.append(r)
    l = max(ll)
    r = min(rl)
    print(max(0,r-l+1))

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

from bisect import bisect_left,bisect

n = int(input())
p = [[int(input())]]
for i in range(n-1):
    now = int(input())
    if now > p[0][-1]:
        p[0].append(now)
    else:
        t = bisect_left(p[0],now)
        k = p[0][t]
        p[0][t] = now
        cou = 1
        while True:
            if cou <= len(p) - 1:
                if k > p[cou][-1]:
                    p[cou].append(k)
                    break
                else:
                    t = bisect_left(p[cou],k)
                    nextk = p[cou][t]
                    p[cou][t] = k
                    k = nextk
                    cou += 1
            elif cou == len(p):
                p.append([k])
                break
print(len(p))

### FIXED CODE ###

from bisect import bisect_left,bisect
 
n = int(input())
p = [-1*int(input())]
for i in range(n-1):
    now = -1*int(input())
    if now >= p[-1]:
        p.append(now)
    else:
        p[bisect(p,now)] = now
print(len(p))
### BUGGY CODE ###

def dfs(tree, v, tv, p, es):
    if v == tv:
        return True
    for e in tree[v]:
        if e[0] == p:
            continue
        if dfs(tree, e[0], tv, v, es):
            es.append(e[1])
            return True
    return False


def get_bit_count(bit):
    return format(bit, 'b').count('1')


def main():
    n = int(input())
    tree = {}
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a not in tree:
            tree[a] = []
        if b not in tree:
            tree[b] = []
        tree[a].append((b, i))
        tree[b].append((a, i))
    m = int(input())
    eset = [0]*m
    for i in range(m):
        u, v = map(int, input().split())
        es = []
        dfs(tree, u-1, v-1, -1, es)
        for e in es:
            eset[i] |= 1 << e

    ans = 0
    for i in range(1 << m):
        mask = 0
        for j in range(m):
            if i >> j & 1:
                mask |= eset[j]
        white = get_bit_count(mask)
        now = 1 << (n-1-white)
        if get_bit_count(i) % 2 == 0:
            ans += now
        else:
            ans -= now
    print(ans)


main()


### FIXED CODE ###

def dfs(tree, v, tv, p, es):
    if v == tv:
        return True
    for e in tree[v]:
        if e[0] == p:
            continue
        if dfs(tree, e[0], tv, v, es):
            es.append(e[1])
            return True
    return False


def main():
    n = int(input())
    tree = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append((b, i))
        tree[b].append((a, i))
    m = int(input())
    eset = [0]*m
    for i in range(m):
        u, v = map(int, input().split())
        es = []
        dfs(tree, u-1, v-1, -1, es)
        for e in es:
            eset[i] |= 1 << e

    ans = 0
    for i in range(1 << m):
        mask = 0
        for j in range(m):
            if i >> j & 1:
                mask |= eset[j]
        white = bin(mask).count('1')
        now = 1 << (n-1-white)
        if bin(i).count('1') % 2 == 0:
            ans += now
        else:
            ans -= now
    print(ans)


main()
### BUGGY CODE ###

s = list(input())
ans = 0
for i in range(len(s)-2):
  if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
    ans +=1
    s[i]="B"
    s[i+1]="C"
    s[i+2]="A"
    l=i-1
    while 0<=l and s[l]=="A":
      s[l]="B"
      s[l+1]="C"
      s[l+2]="A"
      ans+=1
      l-=1
print(ans)

### FIXED CODE ###

s = list(input())
ans = 0
cnta = 0
flagb = 0
flabc= 0
for i in range(len(s)):
  if s[i]=="A":
    if flagb==0:
      cnta+=1
    else:
      cnta=1
      flagb=0
  if s[i]=="B":
    if flagb==0 and cnta:
      flagb=1
    else:
      flagb=0
      cnta=0
  if s[i]=="C":
    if flagb and cnta:
      ans+= cnta
      flagb=0
    else:
      cnta=0
      flagb=0
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
b = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

ans = 0
for i in range(n-1, -1, -1):
    a[i] += ans
    while a[i] % b[i] != 0:
        ans += 1
        a[i] += 1

print(ans)


### FIXED CODE ###

n = int(input())
a = []
b = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

ans = 0
for i in range(n-1, -1, -1):
    a[i] += ans
    mod = a[i] % b[i]
    if mod != 0:
        if a[i] > b[i]:
            ans += b[i] - mod
        else:
            ans += b[i] - a[i]

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

N = int(input())
a = [int(input()) for _ in range(N)]
for i in range(N):
    front = a[:i]
    back = a[i + 1:]
    f_max = max(front) if front else 0
    b_max = max(back) if back else 0
    print(max(f_max, b_max))

### FIXED CODE ###

N = int(input())
a = list()
tmp = [0, 0]

for _ in range(N):
    ai = int(input())
    a.append(ai)
    if ai > tmp[1]:
        tmp[1] = ai
    elif ai > tmp[0]:
        tmp[0] = ai

m = tmp[1]

for ai in a:
    ans = m
    if ai == m:
        ans = tmp[0]
    print(ans)
### BUGGY CODE ###

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

for i in range(Q):
    b, c = map(int, input().split())
    s = 0
    e = N
    h = int((s+e)/2)
    while A[h] != b and s != h :
        if A[h] < b:
            s = h
            h = int((s+e)/2)
        elif A[h] > b:
            e = h
            h = int((s+e)/2)
    for j in range(s, e):
        if A[j] == b:
            A[j] = c
    A.sort()
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
X = [0] * (10**5)

for i in range(N):
    X[A[i]-1] += 1

ans = sum(A)

for j in range(Q):
    b, c = map(int, input().split())
    a = X[b-1]
    X[b-1] = 0
    X[c-1] += a
    ans = ans - a*b + c*a
    print(ans)
### BUGGY CODE ###

N = int(input())
a_ls = list(map(int,input().split(" ")))
N = [0]*N
l = len(a_ls)

# 大きい方からチェック
for i in range(l):
    a = a_ls[-(i+1)]
    s = sum(N[(l-i)-1::(l-i)])%2
    # print(s)
    # print(a)
    if a != s:
        N[-(i+1)]=1
        
sen = ""
for i,n in enumerate(N):
    if n == 1:
        sen += "{} ".format(i+1)

if len(sen) == 0:
    print(0)
else:
    print(sum(N))
    print(sen[:-1])


### FIXED CODE ###

N = int(input())
a_ls = list(map(int,input().split(" ")))
N = [0]*N
l = len(a_ls)

# 大きい方からチェック
for i in range(l):
    a = a_ls[-(i+1)]
    s = sum(N[(l-i)-1::(l-i)])%2
    # print(s)
    # print(a)
    if a != s:
        N[-(i+1)]=1
        
sen = ""
for i,n in enumerate(N):
    if n == 1:
        sen += "{} ".format(i+1)

if len(sen) == 0:
    print(0)
else:
    print(sum(N))
    print(sen[:-1])
### BUGGY CODE ###

n = int(input())
s = input()
 
ans = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
                if j-i == k-j:
                    ans -= 1
                    
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
 
ans = s.count("R") * s.count("G") * s.count("B")
for i in range(n-2):
    for j in range(i+1,n-1):
        k = 2*j-i
        if k < n:
            if s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
                    ans -= 1
                    
print(ans)
### BUGGY CODE ###

from collections import Counter

N = int(input())

c = Counter(list(map(int, input().split())))
D = sorted(list(c.keys()))

x = 0
s = 0
for k in D:
    a = sum([c[d] for d in D if d <= k])
    b = sum([c[d] for d in D if d > k])
    if a == b:
        x = k
    elif a > b and x > 0:
        s = k - x
        break

print(s)

### FIXED CODE ###

from collections import Counter

N = int(input())

c = Counter(list(map(int, input().split())))
D = sorted(list(c.keys()))

x = 0
s = 0
a = 0
b = N
for k in D:
    a += c[k]
    b = N - a
    if a == b:
        x = k
    elif a > b and x > 0:
        s = k - x
        break

print(s)
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = []
B = []
ans = 0
for _ in range(N):
    i = list(map(int,input().split()))
    A.append(i[0])
    B.append(i[1])
while M != 0:
    ind_ = A.index(min(A))
    if M - B[ind_] > 0:
        M -= B[ind_]
        ans = ans + A[ind_]*B[ind_]
        B[ind_] -= B[ind_]
    else:
        ans = ans + A[ind_]*M
        M = 0
        B[ind_] = 0
    if B[ind_] <= 0:
        B.pop(ind_)
        A.pop(ind_)
print(ans)

### FIXED CODE ###

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

AB = [list(map(int,input().split())) for i in range(N)]
AB.sort()
ans = 0
for _ in range(N):
    if AB[_][1] >= M:
        ans += AB[_][0]*M
        break
    else:
        ans += AB[_][0]*AB[_][1]
        M -= AB[_][1]
print(ans)
### BUGGY CODE ###

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

from functools import reduce
from operator import add, mul
result =reduce(mul, P)

if result>10**18:
    print(-1)
else:
    print(result)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
B=1
for i in A:
  B*=i
  if(B>10**18):
    B=-1
    break
print(B)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S-X, X, 0, i])
    Stop.append([T-X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
for _ in range(Q):
    D = int(input())
    i = 0
    while i < len(Stop) and Stop[i][0] <= D:
        time, pos, lr, idx = Stop[i]
        if lr == 0:
            heapq.heappush(q, (pos, idx))
        else:
            notClosed[idx] = True
            while len(q) and notClosed[q[0][1]]:
                aaa = heapq.heappop(q)[1]
        i+=1
    if len(q):
        print(q[0][0])
    else:
        print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S - X, X, 0, i])
    Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][1]]:
            aaa = heapq.heappop(q)[1]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
A0 = list(map(itemgetter(0), A))
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A0, D)

    print(A[idx-1][1])
### BUGGY CODE ###

S = input()
T = input()

dp = [[[] for j in range(len(T)+1)] for i in range(len(S)+1)]
for i, s in enumerate(S):
  for j, t in enumerate(T):
    if s == t:
      dp[i+1][j+1] = dp[i][j]
      dp[i+1][j+1].append(s)
    else:
      if len(dp[i][j+1]) > len(dp[i+1][j]):
        dp[i+1][j+1] = list(''.join(dp[i][j+1]))
      else:
        dp[i+1][j+1] = list(''.join(dp[i+1][j]))

print(''.join(dp[-1][-1]))

### FIXED CODE ###

S = input()
T = input()

dp = [[0] * (len(T)+1) for i in range(len(S)+1)]
for i, s in enumerate(S, 1):
  for j, t in enumerate(T, 1):
    if s == t:
      dp[i][j] = dp[i-1][j-1] + 1
    else:
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = []
while i > 0 and j > 0:
  if dp[i][j] == dp[i][j-1]:
    j -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    ans.append(S[i-1])
    i -= 1
    j -= 1

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

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])

min_A = A[0]

for _ in range(M) :
    B, C = map(int, input().split())
    if C > min_A :
        A += [C] * B
        A = sorted(A)[B:]
        min_A = A[0]

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [[1, int(i)] for i in input().split()]
BC = A + [[int(i) for i in input().split()] for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)

i = 0
res = 0

for B, C in BC :
    if i + B <= N :
        res += C * B
        i += B
    else :
        res += C * (N - i)
        break

print(res)
### BUGGY CODE ###

# ソートして全探索

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(sorted(input())))

c = 0
for i in range(n - 1, -1, -1):
    for j in range(i - 1, -1, -1):
        if arr[i] == arr[j]:
            c += 1

print(c)


### FIXED CODE ###

# じゃあ全部保存していってやるよ
# atcoderのpython3のバージョンが古すぎて(3.4.3)TypeError: unhashable type: 'list'なるのでため息つきながら直した

n = int(input())
d = {}
arr = []
for _ in range(n):
    x = "".join(list(map(str, list(sorted(input())))))
    arr.append(x)
    if x not in d:
        d[x] = 1
    else:
        d[x] += 1

c = 0
for a in arr[:0:-1]:
    if d[a] > 0:
        c += d[a] - 1
        d[a] -= 1

print(c)
### BUGGY CODE ###

def main():
    a,b,q = map(int,input().split())
    A = []
    B = []
    
    for _ in range(a):
        A.append(int(input()))
    
    for _ in range(b):
        B.append(int(input()))
    
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(input())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        p1 = min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr))
        p2 = max(sl,tl)
        p3 = max(sr,tr)
        print(min(p1,p2,p3))

if __name__ == '__main__':
    main()
    
    
    



### FIXED CODE ###

import sys
readline = sys.stdin.readline


def main():
    a,b,q = map(int,readline().split())
    A = [int(readline()) for i in range(a)]
    B = [int(readline()) for i in range(b)]
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(readline())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        print(min(min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr)),max(sl,tl),max(sr,tr)))

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

# -*- coding: utf-8 -*-
from scipy.sparse.csgraph import connected_components
from scipy.sparse import lil_matrix
import collections

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

friend_mtx = lil_matrix((n, n))

friend_cnt = [0] * n
blocked_cnt = [0] * n

for i in range(m):
    a, b = map(int, input().split())
    friend_mtx[a-1, b-1] = 1
    friend_mtx[b-1, a-1] = 1
    friend_cnt[a-1] = friend_cnt[a-1] + 1
    friend_cnt[b-1] = friend_cnt[b-1] + 1

csr_mtx = friend_mtx.tocsr()
num, labels = connected_components(csr_mtx)

for i in range(k):
    c, d = map(int, input().split())
    if labels[c-1] == labels[d-1]:
        blocked_cnt[c-1] = blocked_cnt[c-1] + 1
        blocked_cnt[d-1] = blocked_cnt[d-1] + 1

renketsu_cnt = collections.Counter(labels)

for i in range(n):
    i_label = labels[i]
    renketsu_cnt_i = renketsu_cnt[i_label]
    num_friend = friend_cnt[i]
    num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - num_friend - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        print()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

friend_cnt = [0] * n
blocked_cnt = [0] * n

uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    friend_cnt[a-1] += 1
    friend_cnt[b-1] += 1
    uf.Unite(a-1, b-1)

for i in range(k):
    c, d = map(int, input().split())
    if uf.isSameGroup(c-1, d-1):
        blocked_cnt[c-1] = blocked_cnt[c-1] + 1
        blocked_cnt[d-1] = blocked_cnt[d-1] + 1

for i in range(n):
    renketsu_cnt_i = uf.Count(i)
    num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - friend_cnt[i] - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        print()