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

import itertools

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
MAX = 10 ** 10
dist = [[MAX] * N for _ in range(N)]

for i in range(M):
    dist[A[i]-1][B[i]-1] = C[i]
    dist[B[i]-1][A[i]-1] = C[i]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = 10 ** 10
for per in itertools.permutations(r, R):
    cost = 0
    for i in range(R-1):
        cost += dist[per[i]][per[i+1]]
    ans = min(ans, cost)

print(ans)

### FIXED CODE ###

import itertools

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x) - 1, input().split()))
A = [0] * M
B = [0] * M
C = [0] * M
for i in range(M):
    A[i], B[i], C[i] = map(int, input().split())
MAX = 10 ** 10
dist = [[MAX] * N for _ in range(N)]

for i in range(M):
    dist[A[i]-1][B[i]-1] = C[i]
    dist[B[i]-1][A[i]-1] = C[i]
    
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = 10 ** 10
for per in itertools.permutations(r, R):
    cost = 0
    for i in range(R-1):
        cost += dist[per[i]][per[i+1]]
    ans = min(ans, cost)

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

# D - Lamp

import numpy as np

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

def n_row_lighten(l):
    output_list = []
    left_block_idx = -1
    
    for idx in range(len(l)):
        if l[idx] == "#":
            right_block_idx = idx
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
            output_list.append(0)
            left_block_idx = right_block_idx
            
        if idx == len(l) - 1 and l[idx] == ".":
            right_block_idx = idx + 1
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
        
    return output_list        

def n_matrix_lighten(S):
    output_list = []
    for row in range(len(S)):
        output_list.append(n_row_lighten(S[row]))
    return output_list

n_lighten = n_matrix_lighten(S) + np.array(n_matrix_lighten(S.T)).T - 1
print(np.amax(n_lighten))

### FIXED CODE ###

# D - Lamp

#import numpy as np

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

def trans(M):
    output_list = []
    for col in range(len(M[0])):
        tmp = []
        for row in range(len(M)):
            tmp.append(M[row][col])
        output_list.append(tmp)
    return output_list
            
def n_row_lighten(l):
    output_list = []
    left_block_idx = -1
    
    for idx in range(len(l)):
        if l[idx] == "#":
            right_block_idx = idx
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
            output_list.append(0)
            left_block_idx = right_block_idx
            
        if idx == len(l) - 1 and l[idx] == ".":
            right_block_idx = idx + 1
            for _ in range(right_block_idx - left_block_idx - 1):
                output_list.append(right_block_idx - left_block_idx - 1)
        
    return output_list        

def n_matrix_lighten(S):
    output_list = []
    for row in range(len(S)):
        output_list.append(n_row_lighten(S[row]))
    return output_list

#n_lighten = n_matrix_lighten(S) + np.array(n_matrix_lighten(S.T)).T - 1
ans = 0
tmp1 = n_matrix_lighten(S)
tmp2 = trans(n_matrix_lighten(trans(S)))

for row in range(H):
    for col in range(W):
        ans = max(ans, tmp1[row][col] + tmp2[row][col] - 1)

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

n = int(input())
bs = list(map(int, input().split()))
ans = [0] * n

def chk(numbers, ans, n):
    m = len(numbers)
    if m == 1:
        if numbers == [1]:
            ans[n-1] = 1
            return True
        else:
            return False
    cnt = 0
    for i, b in enumerate(numbers):
        if b == i+1:
            cnt += 1
            ans[n-m] = b
            tempns = numbers.copy()
            tempns.pop(i)
            if chk(tempns, ans, n):
                return True
    if cnt == 0:
        ans[n-m] = 0
    return False

chk(bs, ans, n)

if 0 in ans:
    print(-1)
else:
    ans = ans[::-1]
    for a in ans:
        print(a)

### FIXED CODE ###

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

ans = []

for i in range(n):
    for j in range(n-i, 0, -1):
        if bs[j-1] == j:
            ans.append(j)
            del bs[j-1]
            break
if len(ans) == n:
    ans = ans[::-1]
    for a in ans:
        print(a)
else:
    print(-1)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())

sum = 0
for n in range(A, B+1):
    if (n % C != 0) and (n % D != 0):
        sum += 1
print(sum)

### FIXED CODE ###

import fractions

A, B, C, D = map(int, input().split())

# B以下でC, Dで割り切れるものの個数
b_c = B // C
b_d = B // D

# B以下でCでもDでも割り切れるものの個数
b_c_d = B // ((C*D)//fractions.gcd(C,D))

# A未満でC, Dで割り切れるものの個数
a_c = (A-1) // C
a_d = (A-1) // D

# A未満でCでもDでも割り切れるものの個数
a_c_d = (A-1) // ((C*D)//fractions.gcd(C,D))


count = b_c + b_d - b_c_d - (a_c + a_d - a_c_d)

ans = B-A+1 - count
print(int(ans))
### BUGGY CODE ###

Q = int(input())

def prime(n):
    # 素数列挙
    # nまでの素数をリストで返す(nを含む)
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
        primes.difference_update(range(i*2, n+1, i))
    primes=list(primes)
    return primes

def count_num(n):
    cnt = 0
    prime_list = prime(n)
    prime_set = set(prime_list)
    for x in prime_list:
        if (x+1)//2 in prime_set:
            cnt += 1
    return cnt

for i in range(Q):
    l, r = map(int, input().split())
    print(count_num(r) - count_num(l-1))

### FIXED CODE ###

from itertools import accumulate
Q = int(input())

def prime(n):
    # 素数列挙
    # nまでの素数をリストで返す(nを含む)
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
        primes.difference_update(range(i*2, n+1, i))
    primes=list(primes)
    return primes

prime_set = set(prime(10**5))
ans = []

for i in range(10**5+1):
    if i%2 == 0:
        ans.append(0)
    else:
        if i in prime_set and (i+1)//2 in prime_set:
            ans.append(1)
        else:
            ans.append(0)
ans = list(accumulate(ans))

for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l-1])
### BUGGY CODE ###

from math import pow
def get_table():
    table = []
    for i in range(50):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)

### FIXED CODE ###

from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

for i in range(10, 10000):
    curr = get_power_2019(i)
    table.append(curr)

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)
### BUGGY CODE ###

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

    res = 0
    i = 1

    while i < len(A) - 1:
        if A[i - 1] < A[i] and A[i] > A[i + 1]:
            res += 1
            A = A[i + 1:]
            i = 1
        elif A[i - 1] > A[i] and A[i] < A[i + 1]:
            res += 1
            A = A[i + 1:]
            i = 1
        else:
            i += 1
    
    print(res + 1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    res = 1
    inc = 0
    dec = 0

    for i in range(n - 1):
        if A[i] < A[i+1]:
            inc += 1
        elif A[i] > A[i+1]:
            dec += 1
        
        if inc and dec:
            res += 1
            inc, dec = 0, 0
    
    print(res)

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

N, M = map(int, input().split())
Pref = [[] for i in range(N)]
City = [N+1 for i in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    Pref[p-1].append((y, i))
    City[i] = (p, y)
for i in range(N):
    Pref[i].sort()
for i in range(M):
    first = City[i][0]
    second = Pref[first-1].index((City[i][1], i))
    ans = "{0:06d}".format(first) + "{0:06d}".format(second+1)
    print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
Pref = [1 for i in range(N)]
City = []
Ans = ["" for i in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    City.append((y, p-1, i))
City.sort()
for i in range(M):
    Ans[City[i][2]] =  "{0:06d}".format(City[i][1]+1) + "{0:06d}".format(Pref[City[i][1]])
    Pref[City[i][1]] += 1

for i in range(M):
    print(Ans[i])
### BUGGY CODE ###

N = int(input())
nums = [int(input()) for i in range(N)]
ans = []
count = 0

for num in nums:
    if ans.count(num) == 0:
        ans.append(num)
        count += 1
    else:
        ans.remove(num)
        count -= 1

print(count)


### FIXED CODE ###

N = int(input())
nums = [int(input()) for i in range(N)]
idxs = set(nums)
ans = {idxs.pop() : 0 for i in range(len(idxs))}
count = 0

for num in nums:
    ans[num] += 1

for i in ans.keys():
    ans[i] = (ans[i] % 2)

print(sum(ans.values()))
### BUGGY CODE ###

import sys
rl = sys.stdin.readline
N, W = map(int, rl().split())
dp = [-1]*(W+1)
dp[0] = 0
for _ in range(N):
    w, v = map(int, rl().split())
    for i in range(W-w, -1, -1):
        dpi = dp[i]
        if dpi == -1:
            continue
        if dp[i+w] < dpi + v:
            dp[i+w] = dpi + v
print(max(dp))

### FIXED CODE ###

import sys
rl = sys.stdin.readline
def a():
    N, W = map(int, rl().split())
    dp = [-1]*(W+1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, rl().split())
        for i in range(W-w, -1, -1):
            dpi = dp[i]
            if dpi == -1:
                continue
            if dp[i+w] < dpi + v:
                dp[i+w] = dpi + v
    print(max(dp))
a()
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = []
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])

  leaves = [n for n in nodes if len(n.edges) == 1]

  while True:
    leaf = leaves.pop(0)
    parent = leaf.edges[0]

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self):
    self.edges = set()
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.add(nodes[b - 1])
    nodes[b - 1].edges.add(nodes[a - 1])

  leaves = collections.deque(n for n in nodes if len(n.edges) == 1)

  while True:
    leaf = leaves.popleft()
    parent = leaf.edges.pop()

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


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

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')
from collections import deque
def solve():
    x, y = MI()

    q = deque([(0, 0)])
    mod = 1000000007

    cnt = {(0, 0): 1}
    while len(q) > 0:
        cx, cy = q.popleft()
        d = cnt[(cx, cy)]
        for i in [1, 2]:
            nx = cx + i
            ny = cy + 3 - i
            if nx > x or ny > y:
                continue
            elif (nx, ny) in q:
                cnt[(nx, ny)] += d
            else:
                q.append((nx, ny))
                cnt[(nx, ny)] = d
    print(cnt.get((x, y), 0) % mod)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): return k.join(list(map(str, lst)))
INF = float('inf')

def mcomb(n, k, mod):
    def mfac(l, r, mod):
        ans = l
        for i in reversed(range(r, l)):
            ans *= i
            ans %= mod
        return ans

    A = mfac(n,n-k+1,mod)
    B = mfac(k,1,mod)
    # B = mpow(B,mod-2,mod)
    B = pow(B, mod-2, mod)
    return A * B % mod

def solve():
    x, y = MI()
    if (x + y) % 3 != 0:
        print(0)
        return

    n = (x + y) // 3
    x -= n
    y -= n
    if x < 0 or y < 0:
        print(0)
        return

    mod = 1000000007
    ans = mcomb(x+y, max(x, y), mod)
    print(ans % mod)

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

import numpy as np

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

a = np.full(n, k)

for _ in range(q):
    seikaisha = int(input()) - 1
    a -= 1
    a[seikaisha] += 1

a_tuple = tuple(a)
for sankasha_point in a_tuple:
    if sankasha_point > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np

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

a = np.full(n, k)
plus_point = np.zeros(n, dtype=np.int)

for _ in range(q):
    seikaisha = int(input()) - 1
    plus_point[seikaisha] += 1


a -= q
a += plus_point

for sankasha_point in a:
    if sankasha_point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

a, b, k = map(int, input().split())

for i in range(k):
  if a >= 1:
    a-=1
  elif b >= 1:
    b-=1
print(a,b)

### FIXED CODE ###

a, b, k = map(int, input().split())

if k-a >= 0:
  k = k-a
  a = 0
  if b-k >= 0:
    b = b-k
  else:
    b = 0
else:
  a = a-k
    
print(a, end="")
print(" ", end="")
print(b)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
x = sum(a)
ans = []
for i in range(1,n):
    ans.append(abs(x-2*sum(a[:i])))
print(min(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = float("INF")
X = sum(a)

x = 0
for i in range(n):
    x += a[i]
    if i+1 < n:
        ans = min(ans,abs(X-2*x))
print(ans)
### BUGGY CODE ###

import functools
import fractions
import copy
 
N = int(input())
A_list = list(map(int, input().split()))
values = []
values_list = []
 
for i in range(N):
    values = copy.copy(A_list)
    del values[i]
    gcd = functools.reduce(fractions.gcd, values)
    values_list.append(gcd)
 
print(max(values_list))
 

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
 
def gcd(x,y):
    while y:
        x,y = y, x % y
    return x
    
gcd_left = [0]
gcd_rigth = [0]
gcd_list = []

for i in range(n):
    s = gcd(gcd_left[i], a[i])
    gcd_left.append(s)
    
for i in range(n):
    t = gcd(gcd_rigth[i], a[-i-1])
    gcd_rigth.append(t)

for i in range(n):
    v = gcd(gcd_left[i], gcd_rigth[n-1-i])
    gcd_list.append(v)

print(max(gcd_list))
### BUGGY CODE ###

n,x = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for i in range(n-1):
    while a[i] + a[i+1] > x:
        a[i+1] += -1
        ans += 1
print(ans)


### FIXED CODE ###

n,x = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
    if a[i] >= x:
        ans += a[i]-x
        a[i] = x
for j in range(n-1):
    if a[j] + a[j+1] >= x:
        d = a[j]+ a[j+1] - x
        ans += d
        a[j+1] -= d
print(ans)
### BUGGY CODE ###

n = int(input())

print(sum(range(1, n + 1)) - n)

### FIXED CODE ###

n = int(input())

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

import numpy as np

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

i = 0
total_cost = 0
 
a = np.zeros(N, int)
a[0] = 0
a[1] = abs(hs[1] - hs[0])

for i in range(2, N):
    #a[i] = min(a[max(i-2,0)] + abs(hs[i] - hs[max(i-2,0)]),
    #           a[max(i-1,0)] + abs(hs[i] - hs[max(i-1,0)]))
    
    #b = np.zeros(K, int)
    #for j in range(K):
    #    b[j] = a[max(i-(j+1),0)] + abs(hs[i] - hs[max(i-(j+1),0)])
    
    bmin = float('inf')
    for j in range(K):
        bmin = min(bmin, a[max(i-(j+1),0)] + abs(hs[i] - hs[max(i-(j+1),0)]))    
    
    a[i] = bmin
print(a[-1])

### FIXED CODE ###

import numpy as np

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

a = np.zeros(N, int)
a[0] = 0
a[1] = abs(hs[1] - hs[0])

if N == 2:
    print(a[-1])
else:
    for i in range(2, N):
        b = a[max(i-K,0):i] + np.abs(hs[i] - hs[max(i-K,0):i])
        a[i] = np.min(b)
    print(a[-1])
### BUGGY CODE ###

a, b, x = map(int, input().split())
cnt = 0
for i in range(a, b+1):
  if i % x == 0:
    cnt += 1
print(cnt)

### FIXED CODE ###

a, b, x = map(int, input().split())
def f(n, x):
  if n == -1:
    return 0
  return n//x+1
print(f(b, x) - f(a-1, x))
### BUGGY CODE ###

n=int(input())
S=list(input())
w=n-S.count('W')
p=[]
for i in range(n):
    s=w-i+2*S[:i].count('W')
    p.append(s)

print(min(p))


### FIXED CODE ###

n=int(input())
S=list(input())
R=[0]
for i in range(n):
    R.append(R[i]+(S[i]=='W'))
print(min([R[i]+n-i-1-(R[-1]-R[i+1]) for i in range(n)] ))
### BUGGY CODE ###

N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

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 set(self):
      [self.find(self.parents[i]) for i in range(self.n)]
      
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(len(uf.members(i)) - (len(uf.members(i)+block_list[i])-len(set(uf.members(i)+block_list[i]))))
print(*ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
block_list = [[i] for i in range(N)]

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 members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  block_list[a-1].append(b-1)
  block_list[b-1].append(a-1)
for i in range(K):
  a, b = map(int, input().split())
  if uf.same(a-1, b-1):
    block_list[a-1].append(b-1)
    block_list[b-1].append(a-1)
ans = []
for i in range(N):
  ans.append(uf.size(i) - len(block_list[i]))
print(*ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N, M, K = [int(s) for s in input().split()]
n = 0
A = [0]
for s in input().split():
    n = n + int(s)
    A.append(n)

n = 0
B = [0]
for s in input().split():
    n = n + int(s)
    B.append(n)

ans = 0
for i, a_time in enumerate(A):
    if a_time <= K:
        for j, b_time in enumerate(B):
            read_time = a_time + b_time
            if read_time > K:
                if ans <= i + j - 1:
                    ans = i + j - 1
                break
    else:
        break

if ans == 0:
    if A[1] < K:
        ans = N + M
    elif B[1] < K:
        ans = N + M

print(ans)

### FIXED CODE ###

import sys

N, M, K = [int(s) for s in sys.stdin.readline().split()]
n = 0
A = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    A.append(n)

n = 0
B = [0]
for s in sys.stdin.readline().split():
    n = n + int(s)
    B.append(n)

ans = 0
for i in range(N + 1):
    if A[i] > K:
        break
    for j in range(M, -1, -1):
        if A[i] + B[j] <= K:
            ans = max(ans, i + j)
            M = j
            break

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

n=int(input())
tmp = 0
while n > 0:
    tmp += (n % 10)
    n = n // 10
if tmp % 9 == 0:
    ans = 'Yes'
else:
    ans ='No'
print(ans)

### FIXED CODE ###

n=input()
n_arr = [int(n[i]) for i in range(len(n))]
tmp = 0
for i in n_arr:
    tmp += i
if tmp % 9 == 0:
    ans = 'Yes'
else:
    ans ='No'
print(ans)