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

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

#N=len(sticks)
sticks.sort(reverse = True)
count = 0
fj = fk = True
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if not fj:
            fj=True
            break
        else:
            for k in range(j+1,N):
                #stick[i]>j>k
                if sticks[i]<sticks[j]+sticks[k]:
                    count += 1
                else:
                    if j+1 == k :
                        fj = False
                    break
        
print(count)

### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

N,HP=map(int,input().split())
listK=[]
listN=[]

for i in range(N):
    k,n=map(int,input().split())
    listK.append(k)
    listN.append(n)
listK.sort(reverse=True)
listN.sort(reverse=True)
cnt=0
for j in range(N):
    if listN[j]>=max(listK):
        HP=HP-listN[j]
        cnt+=1
        if HP<=0:
            print(cnt)
            exit()
    else:
        break

if HP%(listK[0])==0:
    print(cnt+int(HP/listK[0]))
else:
    print(cnt+1+int(HP/listK[0]))

### FIXED CODE ###

n,h=map(int,input().split())
slash=[]
throw=[]
for i in range(n):
    x,y=map(int,input().split())
    slash.append(x)
    throw.append(y)
 
slash.sort(reverse=True)
throw.sort(reverse=True)
attack=0
for i in range(n):
    if throw[i]>=slash[0]:
        h-=throw[i]
        attack+=1
        if h<=0:
            print(attack)
            exit()
    else :
        break
 
attack+=int((h+slash[0]-1)/(slash[0]))
print(attack)
### BUGGY CODE ###

from collections import Counter
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = set(A)
d = Counter(A)
num = len(B) - K
ans = 0
for i in range(1, num+1):
    ans += d.most_common()[-i][1]
print(ans)

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = set(A)
d = Counter(A)
num = len(B) - K
ans = 0
c = d.most_common()
for i in range(1, num+1):
    ans += c[-i][1]
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


n = int(readline())
a = list(map(int, readline().split()))
a = a[::-1]
cnt = [0] * n
ans = []
for i in range(n):
    if cnt[n - i - 1] % 2 != a[i]:
        ans.append(n - i)
        memo = make_divisors(n - i)
        for j in range(len(memo)):
            cnt[memo[j] - 1] += 1
print(len(ans))
print(*ans[::-1])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


n = int(readline())
a = list(map(int, readline().split()))
a = a[::-1]
cnt = [0] * n
ans = []
for i in range(n):
    if cnt[n - i - 1] % 2 != a[i]:
        ans.append(n - i)
        memo = make_divisors(n - i)
        for j in range(len(memo)):
            cnt[memo[j] - 1] += 1
print(len(ans))
print(*ans[::-1])
### BUGGY CODE ###

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

def f(n):
    n = str(n).zfill(3)
    # print(n)
    found = False
    for i in range(len(S)):
        if S[i] == n[0]:
            found = True
            break
    if found == False:
        return 0
    
    found = False
    for j in range(i+1, len(S)):
        if S[j] == n[1]:
            found = True
            break
    if found == False:
        return 0

    found = False
    for k in range(j+1, len(S)):
        if S[k] == n[2]:
            found = True
            break
    if found:
        return 1
    return 0

ans = 0
for i in range(1000):
    ans += f(i)

print(ans)




### FIXED CODE ###

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

def f(n):
    n = str(n).zfill(3)
    # print(n)
    found = False
    for i in range(len(S)):
        if S[i] == n[0]:
            found = True
            break
    if found == False:
        return 0
    
    found = False
    for j in range(i+1, len(S)):
        if S[j] == n[1]:
            found = True
            break
    if found == False:
        return 0

    found = False
    for k in range(j+1, len(S)):
        if S[k] == n[2]:
            found = True
            break
    if found:
        return 1
    return 0

ans = 0
for i in range(1000):
    ans += f(i)

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

import heapq

n, m = map(int, input().split())
list_score = list(map(int, input().split()))
list_kard = [ list(map(int,input().split(" "))) for i in range(m)]

heapq.heapify(list_score)

for i in range(m):
    k = list_kard[i]
    for _ in range(k[0]):
        if list_score[0] < k[1]:
            heapq.heappop(list_score)
            heapq.heappush(list_score, k[1])

print(sum(list_score))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
list_score = list(map(int, input().split()))
list_kard = [list(map(int, input().split(" "))) for i in range(m)]

list_kard.sort(key=lambda x: x[1], reverse=True)
heapq.heapify(list_score)

for i in range(m):
    k = list_kard[i]
    for _ in range(k[0]):
        if list_score[0] < k[1]:
            heapq.heappop(list_score)
            heapq.heappush(list_score, k[1])
        else:
            break

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

import sys
sys.setrecursionlimit(10**7)
n,m,p = map(int,input().split())
E1 = [[] for i in range(n)]
E2 = [[] for i in range(n)]
edge = []
for i in range(m):
    a,b,c = map(int,input().split())
    c = p-c
    a -= 1
    b -= 1
    E1[a].append(b)
    E2[b].append(a)
    edge.append((a,b,c))

dis1 = [False]*n
def dfs1(x):
    if dis1[x] == False:
        dis1[x] = True
        for nex in E1[x]:
            dfs1(nex)

dis2 = [False]*n
def dfs2(x):
    if dis2[x] == False:
        dis2[x] = True
        for nex in E2[x]:
            dfs2(nex)

dfs1(0)
dfs2(n-1)

ok = []
for i in  range(n):
    if dis1[i] and dis2[i]:
        ok.append(True)
    else:
        ok.append(False)
nedge = []
for a,b,c in edge:
    if ok[a] and ok[b]:
        nedge.append((a,b,c))

def belw():
    dis = [float("INF")]*n
    dis[0] = 0
    count = 0
    check = True

    while check:
        check = False
        for a,b,c in nedge:
            
            if dis[a] != float("INF") and dis[b] > dis[a]+c:
                check = True
                dis[b] = dis[a]+c
        count += 1

        if count > n+1 and check:
            return float("INF")
    
    return -dis[-1]

ans = belw()
if ans == float("INF"):
    print(-1)
else:
    print(max(ans,0))











### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m,p = map(int,input().split())
E1 = [[] for i in range(n)]
E2 = [[] for i in range(n)]
edge = []
for i in range(m):
    a,b,c = map(int,input().split())
    c = p-c
    a -= 1
    b -= 1
    E1[a].append(b)
    E2[b].append(a)
    edge.append((a,b,c))

dis1 = [False]*n
def dfs1(x):
    if dis1[x] == False:
        dis1[x] = True
        for nex in E1[x]:
            dfs1(nex)

dis2 = [False]*n
def dfs2(x):
    if dis2[x] == False:
        dis2[x] = True
        for nex in E2[x]:
            dfs2(nex)

dfs1(0)
dfs2(n-1)

ok = []
for i in  range(n):
    if dis1[i] and dis2[i]:
        ok.append(True)
    else:
        ok.append(False)
nedge = []
for a,b,c in edge:
    if ok[a] and ok[b]:
        nedge.append((a,b,c))

def belw():
    dis = [float("INF")]*n
    dis[0] = 0
    count = 0
    check = True

    while check:
        check = False
        for a,b,c in nedge:
            
            if dis[a] != float("INF") and dis[b] > dis[a]+c:
                check = True
                dis[b] = dis[a]+c
        count += 1

        if count > n+1 and check:
            return float("INF")
    
    return -dis[-1]

ans = belw()
if ans == float("INF"):
    print(-1)
else:
    print(max(ans,0))
### BUGGY CODE ###

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

for i in range(n):
    ans = a.count(i+1)
    print(ans)
    if ans > 0:
        a.remove(i+1)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = 1
count = 0
for i in a:
    if i == c:
        count += 1
    else:
        print(count)
        if i-c-1 > 0:
            for _ in range(i-c-1):
                print(0)
        c = i
        count = 1
print(count)
for _ in range(n-a[-1]):
    print(0)
### BUGGY CODE ###

import math

k = int(input())
num = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            d = math.gcd(a,b)
            num += math.gcd(d,c)

print(num)

### FIXED CODE ###

import math
 
k = int(input())
num = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            d = math.gcd(a,b)
            num += math.gcd(d,c)
 
print(num)
### BUGGY CODE ###

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

L.sort()

count = 0
for i in range(0, N - 2):
    for p in range(i + 1, N - 1):
        left = p + 1
        right = N - 1
        tmp = (left + right) // 2
        if left == right:
            if L[i] + L[p] > L[left]:
                count += (left - p)
                break
        while 'true':
            if L[i] + L[p] > L[tmp]:
                left = tmp
                tmp = (left + right) // 2
            else:
                right = tmp
                tmp = (left + right) // 2
            if abs(right - left) <= 1:
                if L[i] + L[p] > L[right]:
                    count += (right - p)
                    break
                elif L[i] + L[p] > L[left]:
                    count += (left - p)
                    break
                else:
                    break
print(count)

### FIXED CODE ###

import bisect

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

L.sort()

count = 0
for i in range(0, N - 2):
    for p in range(i + 1, N - 1):
        count += bisect.bisect_left(L, L[i] + L[p]) - p - 1
print(count)
### BUGGY CODE ###

n=int(input())
lst=list(map(int,input().split()))
# print(sum(lst))
tem=0
for i in range(n-1):
    for j in range(i+1,n):
        tem+=(lst[i] % (10**9+7) )*(lst[j] % (10**9+7) )
        # print(tem)
print(tem % (10**9 +7))

### FIXED CODE ###

n=int(input())
lst=list(map(int,input().split()))
aa=sum(lst) % (10**9+7)
# print(sum(lst) % (10**9+7) )
new_lst=[]
temp_1=aa
for i in range(n-1):
    temp_1-=lst[i]
    new_lst.append(temp_1)
# print(new_lst)

tem=0
for i in range(n-1):
    tem+=(lst[i] )*new_lst[i]
        # print(tem)
print(tem % (10**9 +7))
### BUGGY CODE ###

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

Mh = [[-1 for _ in range(W)] for _ in range(H)]
Mw = [[-1 for _ in range(W)] for _ in range(H)]

for h in range(H):
    w = 0
    while w < W:
        if S[h][w] == "#":
            w += 1
            continue
        start = w
        count = 0
        while w + count < W and S[h][w + count] == ".":
            count += 1
        for x in range(start, w + count):
            Mh[h][x] = count
        w = w + count


for w in range(W):
    h = 0
    while h < H:
        if S[h][w] == "#":
            h += 1
            continue
        start = h
        count = 0
        while h + count < H and S[h+count][w] == ".":
            count += 1
        for x in range(start, h + count):
            Mw[x][w] = count
        h = h + count

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, Mh[h][w]+Mw[h][w] -1)

print(ans)

### FIXED CODE ###

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

Mh = [[-10000000 for _ in range(W)] for _ in range(H)]
Mw = [[-10000000 for _ in range(W)] for _ in range(H)]

for h in range(H):
    w = 0
    while w < W:
        if S[h][w] == "#":
            w += 1
            continue
        start = w
        count = 0
        while w + count < W and S[h][w + count] == ".":
            count += 1
        for x in range(start, w + count):
            Mh[h][x] = count
        w = w + count


for w in range(W):
    h = 0
    while h < H:
        if S[h][w] == "#":
            h += 1
            continue
        start = h
        count = 0
        while h + count < H and S[h+count][w] == ".":
            count += 1
        for x in range(start, h + count):
            Mw[x][w] = count
        h = h + count

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, Mh[h][w]+Mw[h][w] -1)

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

n = int(input())
mod = 10**9+7
a = list(map(int,input().split()))
m = 2**59
ans = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for j in range(n):
        if a[j]//m == 1:
            c1 += 1
            a[j] -= m
        else:
            c0 += 1
    ans += (c0*c1*m)%mod
    #print(c0,c1,m,ans)
    ans %= mod
    m //= 2
print(ans)

### FIXED CODE ###

n = int(input())
mod = 10**9+7
a = list(map(int,input().split()))
m = 2**59
ans = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for j in range(n):
        if a[j]//m == 1:
            c1 += 1
            a[j] -= m
        else:
            c0 += 1
    ans += (c0*c1*m)%mod
    #print(c0,c1,m,ans)
    ans %= mod
    m //= 2
print(ans)
### BUGGY CODE ###

n, p = map(int, input().split())
out=1
tm = int(pow(p, 1/n))
for i in range(2,tm+1):
    while p%(i**n)==0:
        p = p//(i**n)
        out *= i
        
    if p < i**n:
        break
print(out)

### FIXED CODE ###

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

if n==1:
    print(p)
else:
    out=1
    tm = int(pow(p, 1/n))
    for i in range(2,tm+1):
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
    print(out)
### BUGGY CODE ###

INF = 10**10

def warshall_floyd(d):
    # d[i][j]: ij間の最小コスト
    # i=jのとき0, i!=jのときINFで初期化
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

N, M, L = map(int, input().split())
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    dist[a][b] = c; dist[b][a] = c
dist = warshall_floyd(dist)

dist2 = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dist2[i][i] = 0
        else:
            if dist[i][j] <= L:
                dist2[i][j] = 1
dist2 = warshall_floyd(dist2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1; t -= 1
    if dist2[s][t] == INF:
        print(-1)
    else:
        print(dist2[s][t]-1)

### FIXED CODE ###

INF = 10**10

def warshall_floyd(d):
    # d[i][j]: ij間の最小コスト
    # i=jのとき0, i!=jのときINFで初期化
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

N, M, L = map(int, input().split())
dist = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1; b -= 1
    dist[a][b] = c; dist[b][a] = c
dist = warshall_floyd(dist)

dist2 = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dist2[i][i] = 0
        else:
            if dist[i][j] <= L:
                dist2[i][j] = 1
dist2 = warshall_floyd(dist2)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1; t -= 1
    if dist2[s][t] == INF:
        print(-1)
    else:
        print(dist2[s][t]-1)
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

K = int(input())

GCD = [[0]*200 for i in range(200)]
for i in range(200):
    for j in range(200):
        GCD[i][j] = gcd(i+1, j+1)

tot = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            s = GCD[j-1][k-1]
            t = GCD[i-1][s-1]
            tot += t
print(tot)


### FIXED CODE ###

K = int(input())

GCD = [[0]*200 for i in range(200)]
def gcd(x, y):
    if GCD[x-1][y-1] == 0:
        if y == 0:
            return x
        else:
            return gcd(y, x % y)
    else:
        return GCD[x-1][y-1]

tot = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        s = gcd(i, j)
        if s != 1:
            for k in range(1, K+1):
                t = gcd(k, s)
                tot += t
        else:
            tot += K
print(tot)
### BUGGY CODE ###

A, B, K = map(int,input().split())
for i in range(A, B + 1):
  if i < A + K or i > B - K: print(i) 


### FIXED CODE ###

A, B, K = map(int,input().split())
for i in range(A, min(A + K, B + 1)):
  print(i) 
for i in range(max(B - K, A) , B):
  if i + 1 >= A + K: print(i + 1)
### BUGGY CODE ###

import math
N = int(input())
A = [0 for _ in range(N)]
u = math.floor((2*N)**0.5)
for x in range(1,u+1):
    for y in range(1,u+1):
        for z in range(1,u+1):
            c = x**2+y**2+z**2+x*y+y*z+z*x
            if c <= N:
                A[c-1] += 1
for i in range(N):
    print(A[i])

### FIXED CODE ###

import math
N = int(input())
A = [0 for _ in range(N)]
for x in range(1,math.floor(N**0.5)+1):
    for y in range(1,math.floor((N-x**2)**0.5)+1):
        for z in range(1,math.floor((N-x**2-y**2)**0.5)+1):
            c = x**2+y**2+z**2+x*y+y*z+z*x
            if c <= N:
                A[c-1] += 1
for i in range(N):
    print(A[i])
### BUGGY CODE ###

#Python

N = input()
#print N

a = [[0 for j in range(N+1)] for i in range(N+1)]

for i in range(N-1):
	l=map(int, raw_input().split())
	#print l[0]
	#print l[1]
	a[l[0]][l[1]]=1
	a[l[1]][l[0]]=1
#print a


v=(N+1)*[0]
kyori=(N+1)*[0]


def visit(i):
	v[i]=1
	#print v

	for j in range(1,N+1):

		#print "*i::"+str(i)+" "+"j::"+str(j)
		if a[i][j] == 1 and v[j] == 0:
			#print str(i)+"==>"+str(j)

			kyori[j]=kyori[i]+1

			#print "dist::"+str(dist)
			visit(j)


visit(1)
kyori_from_start=kyori
#print kyori_from_start


#Initialize
v=(N+1)*[0]
kyori=(N+1)*[0]


visit(N)
#print kyori

f_p=0
s_p=0
for k in range(1,N+1):
	if kyori_from_start[k]<=kyori[k]:
		f_p+=1
	else:
		s_p+=1

#print f_p
#print s_p

if f_p>s_p:
	print 'Fennec'
else:
	print 'Snuke'

### FIXED CODE ###

# -*- coding: utf-8 -*-
#Python
import sys

N=input()
adj=[[] for i in range(N+1)]

#隣接リスト
for i in range(N-1):
    x,y=list(map(int,raw_input().split()))
    adj[x].append(y)
    adj[y].append(x)

#print adj

#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist=(N+1)*[0]


#先頭から深さ優先探索
S.append(1)
while len(S) != 0:
	#print S
	v=S.pop()
	#print v
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				dist[u]=dist[v]+1
				#print S

#print dist



#訪問判別フラグ
F=(N+1)*[0]

#Stack
S=[]

#距離
dist2=(N+1)*[0]

#最後から深さ優先探索
S.append(N)
while len(S) != 0:
	#print S
	v=S.pop()
	#print v
	
	if F[v]==0:
		F[v]=1
		#print F
		for u in adj[v]:
			#print "u::"+str(u)
			if F[u]==0:
				S.append(u)
				dist2[u]=dist2[v]+1
				#print S

#print dist2



f_p=0
s_p=0
for k in range(1,N+1):
	if dist[k]<=dist2[k]:
		f_p+=1
	else:
		s_p+=1


if f_p>s_p:
	print 'Fennec'
else:
	print 'Snuke'
### BUGGY CODE ###

N, M, L = map(int,input().split())
rd = [[] for _ in range(N+1)]
rc = [[] for _ in range(N+1)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if c <= L:
        rd[a].append(b)
        rc[a].append(c)
        rd[b].append(a)
        rc[b].append(c)

Q = int(input())
S = []
T = []
for _ in range(Q):
    s,t = map(int,input().split())
    S.append(s)
    T.append(t)

ZO = [[-1 for i in range(N+1)] for i in range(N+1)]
NP = [[10**9+1 for i in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    for j in range(len(rd[i])):
        d = rd[i][j]
        c = rc[i][j]
        NP[i][d] = 0
        ZO[i][d] = L - c

up = True
while up:
    up = False
    for i in range(1,N+1):
        for j in range(1,N+1):
            if ZO[i][j] < 0: continue
            for k in range(len(rd[j])):
                d = rd[j][k]
                if d == i: continue
                c = rc[j][k]
                if ZO[i][j] < c:
                    nnp = NP[i][j] + 1
                    nzo = L - c
                else:
                    nnp = NP[i][j]
                    nzo = ZO[i][j] - c
                if NP[i][d] > nnp or NP[i][d] == nnp and ZO[i][d] < nzo:
                    ZO[i][d] = nzo
                    NP[i][d] = nnp
                    up = True

for i in range(Q):
    if NP[S[i]][T[i]] > 10**9:
        print (-1)
    else:
        print(NP[S[i]][T[i]])

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


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

from collections import deque
n,m,k=map(int,input().split())

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	F[a-1].add(b-1)
	F[b-1].add(a-1)
for i in range(k):
	c,d=map(int,input().split())
	B[c-1].add(d-1)
	B[d-1].add(c-1)
	
T=[[] for i in range(n)]
D=[0]*n
for i in range(n):
	if D[i]==1:
	    continue
	que=deque([])
	que.append(i)
	T[i].append(i)
	while que:
	    p=que.popleft()
	    for np in F[p]:
	        if D[np]!=1:
	            que.append(np)
	            T[i].append(np)
	            D[np]=1

S=[[] for i in range(n)]
for i in range(n):
    if T[i]:
        for t in T[i]:
            S[t]=set(T[i][:])
            S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(F[i])-len(set(S[i])&set(B[i]))
print(*R)

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	F[a].add(b)
	F[b].add(a)
for i in range(k):
	c,d=map(int,input().split())
	c,d=c-1,d-1
	B[c].add(d)
	B[d].add(c)
	
T=[set() for i in range(n)]
D=[0]*n
R=[0]*n

for i in range(n):
    if D[i]:
        continue
    que=deque([])
    que.append(i)
    S=set()
    S.add(i)
    while que:
        p=que.popleft()
        for np in F[p]:
            if D[np]!=1:
                que.append(np)
                S.add(np)
                D[np]=1
    for s in S:
        R[s]=len(S)-len(F[s])-len(S&B[s])-1

print(*R)