Harryxun/stf_run huggingface dataset:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def seq():
    a = 1
    while True:
        yield a
        a += 1

def dfs(here, went, connect, discovery, low, answer, seq):
    went |= {here}
    discovery[here] = low[here] = next(seq)
    child = 0
    for con in connect[here]:
        if con not in went:
            parent[con] = here
            child += 1
            dfs(con, went, connect, discovery, low, answer, seq)
            low[here] = min(low[here], low[con])
            if discovery[here] < low[con]:
                answer[min(here,con)].append(max(here,con))
        elif parent[here] != con:
            low[here] = min(low[here], discovery[con])

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = defaultdict(list)
new_seq = seq()
went = set()
discovery = [0 for n in range(vertices)]
low = [float("inf") for n in range(vertices)]
parent = [None for n in range(vertices)]
dfs(0, went, connect, discovery, low, answer, new_seq)

for k in range(answer.keys()):
    for n in range(answer[k]):
        print(k,n)

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

def seq():
    a = 1
    while True:
        yield a
        a += 1

def dfs(here, went, connect, discovery, low, answer, seq):
    went |= {here}
    discovery[here] = low[here] = next(seq)
    child = 0
    for con in connect[here]:
        if con not in went:
            parent[con] = here
            child += 1
            dfs(con, went, connect, discovery, low, answer, seq)
            low[here] = min(low[here], low[con])
            if discovery[here] < low[con]:
                answer[min(here,con)].append(max(here,con))
        elif parent[here] != con:
            low[here] = min(low[here], discovery[con])

vertices, edges = (int(n) for n in input().split(" "))
connect = defaultdict(list)
for _ in range(edges):
    v1, v2 = (int(n) for n in input().split(" "))
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = defaultdict(list)
new_seq = seq()
went = set()
discovery = [0 for n in range(vertices)]
low = [float("inf") for n in range(vertices)]
parent = [None for n in range(vertices)]
dfs(0, went, connect, discovery, low, answer, new_seq)

for k in sorted(answer.keys()):
    for n in sorted(answer[k]):
        print(k,n)
X,Y=int(input())
print(X+Y//2)

### FIXED CODE ###

X,Y=map(int,input().split())
print(X+Y//2)
N = list(map(int,input().split()))
math = N[0] * N[1]
 if math % 2 == 1:
  return "Odd"
 else:
  return "Even"

### FIXED CODE ###

N = list(map(int,input().split()))
math = N[0] * N[1]
if math % 2 == 1:
  print("Odd")
else:
  print("Even")
import sys
import numpy as np

MOD = 10 ** 9 + 7

n, *a = map(int, sys.stdin.read().split())
a = np.array(a, dtype=np.int64)

def main():
    b = a >> np.arange(61).reshape(-1, 1) & 1
    x = np.count_nonzero(b, axis=1)
    x = x * (n - x) % MOD
    # x *= 2 ** np.arange(60) % MOD
    for i in range(1, 61):
        x[i] *= pow(2, i, MOD)
    x %= MOD
    ans = np.sum(x) % MOD
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

### FIXED CODE ###

import sys
import numpy as np

MOD = 10 ** 9 + 7

N, *A = map(int, sys.stdin.read().split())
A = np.array(A, dtype=np.int64)

def main():
    answer = 0
    for n in range(60):
        B = (A >> n) & 1
        x = np.count_nonzero(B)
        y = N - x
        x *= y
        x *= pow(2, n, MOD)
        answer += x
    answer %= MOD
    return answer

if __name__ == '__main__':
    ans = main()
    print(ans)
# -*- coding: utf-8 -*-
# Nの取得
index = int(input())

# n回ループして配列に入れる
max = 0
other = 0
for i in range(n):
  tmp = input()
  max = tmp if tmp > max else other = other +  tmp

print("Yes") if max < tmp else print("No")



### FIXED CODE ###

# -*- coding: utf-8 -*-
# Nの取得
index = int(input())

# n回ループして配列に入れる
maximum = 0
other = 0
inputList = input().split()
for i in range(index):
    tmp = int(inputList[i])
    if tmp > maximum:
        maximum = tmp
        other = other + maximum
    else:
        other = other + tmp

if maximum < other - maximum:
    print("Yes")
else:
    print("No")
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
start,i=1,0
root=[1]

for j in range(k):
  start=A[start-1]
  if start in root:
    i = start
    break
  root.append(start)
  
if k <= len(root):
  print(root[k-1])
else:
  newroot=root[i-1:]
  print(newroot)
  ans=(k-len(root))%len(newroot)
  print(newroot[ans])

### FIXED CODE ###

n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
start,steps=1,0
root=dict()

while start not in root and steps < k:
  root[start]=steps
  steps+=1
  start=A[start-1]

if steps == k:
  print(start)
else:
  pa = steps-root[start]
  ans= root[start] + (k-steps)%pa
  root={v: k for k, v in root.items()}
  print(root[ans])
a=34

if a==int
print(6)

### FIXED CODE ###

from fractions import Fraction

a=input()
a=a.split()

X=int(a[0])
Y=int(a[1])

x=Fraction(4*X-Y,2)
y=Fraction(Y-2*X,2)

if x-round(x)==0 and x >= 0:
  if y-round(y)==0 and y >= 0:
    print("Yes")
  else :
    print("No")
else:
  print("No")
n,m,q = map(int,input().split())
a = [0 for i in range(q)]
for i in range(q):
    a[i] = list(map(int,input().split()))
for i in range(1,m+1):
    for j in range(i,m+1):
        for k in range(j,m+1):
            for s in range(k,m+1):
                for p in range(s,m+1):
                    for l in range(p,m+1):
                        for e in range(l,m+1):
                            for u in range(e,m+1):
                                for v in range(u,m+1):
                                    b = [1,f,c,k,s,p,l,e,u,v]
                                    nn = 0
                                    for h in range(q):
                                        if b[a[h][1]-1] - b[a[h][0]-1] == a[h][2]:
                                            nn += a[h][3]
                                    ans = max(ans,nn)
print(ans)

### FIXED CODE ###

N = int(input())
alist = a = [input() for i in range(N)]
alist.sort()
p = 0
for i in range(N-1):
    if alist[i] != alist[i+1]:
        p = p +1
print(p+1)
number = input().split(" ")
A = int(number[0])
P = int(number[1])
apple = (A * 3) + P
print(math.floor(apple / 2))

### FIXED CODE ###

import math

number = input().split(" ")
A = int(number[0])
P = int(number[1])
apple = (A * 3) + P
print(math.floor(apple / 2))
# -*- coding: utf-8 -*-
def main():
    n, q = inputAsIntArr()
    s = input()

    idxes = []
    for i in range(n):
        if s[i] != 'A':
            continue
        if s[i+1] == 'C':
            idxes.append(i)
            i += 1

    num_acs = ""
    for i in range(q):
        li, ri = inputAsIntArr()
        num_ac = len([v for v in idxes if li-2 < v < ri-1])
        num_acs += str(num_ac) + "\n"

    print(num_acs.strip())


def inputAsIntArr():
    return [int(i) for i in input().split()]


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split())
    s = input()

    # 累積出現数を格納: 指定される番号が1始まりなのでズラして格納
    p = [0] * (n+1)
    for i in range(n):
        p[i+1] = p[i] + (1 if s[i:i+2] == "AC" else 0)

    for i in range(q):
        l, r = map(int, input().split())
        # 終端(=l-1)から始端-1(=r-1)の累積出現数を引いた数が指定区間内での出現回数
        print(p[r-1] - p[l-1])


if __name__ == '__main__':
    main()
a,b =map(int,input(),split())
if a<=8 or b<=8:
  print("Yay!")
else:
  print(":(")



### FIXED CODE ###

a,b=map(int,input().split())
if a<=8 and b<=8:
  print("Yay!")
else:
  print(":(")
#abc090 a 
c=[]
for i in range(3):
    line=list(input().split())
print(c[0][0]+c[1][1]+c[2][2])

### FIXED CODE ###

#abc090 a
c=[]
for i in range(3):
    line=input()
    c.append(line)
print(c[0][0]+c[1][1]+c[2][2])
s = input()
t = s[::-1]
n = len(s)
a = s[:(N - 1) // 2]
b = t[:(n + 3) // 2]

if s == t and a == a[::-1] and b == b[::-1]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
t = s[::-1]
n = len(s)
a = s[:(n - 1) // 2]
b = t[:(n - 1) // 2]

if s == t and a == a[::-1] and b == b[::-1]:
    print('Yes')
else:
    print('No')
import sys
input()
x = list(map(int,sys.stdin.readlines().split()))
print("{0} {1} {2}".format(min(x),max(x),sum(x)))

### FIXED CODE ###

import sys
input()
x = list(map(int,sys.stdin.readline().split()))
print("{0} {1} {2}".format(min(x),max(x),sum(x)))
import math

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

if a ** 2 * b * 0.5 < x:
    d = a ** 3 / (2 * (a ** 2 * b - x))
else:
    d = 2 * x / (a * b ** 2)
print(90 - math.atan(d) * 180 / math.pi)


### FIXED CODE ###

from math import atan, pi
a, b, x = map(int, input().split())

if x > (a ** 2 * b / 2):
    print(atan(2 * (a ** 2 * b - x) / a ** 3) * 180 / pi)
else:
    print(atan((a * b ** 2) / (2 * x)) * 180 / pi)
#%%
import collections

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

l = []
for i in range(n):
    for j in range(n):
        tmp = str(x[i]-x[j]) + ' ' + str(y[i]-y[j])
        l.append(tmp)

c = collections.Counter(l)
a = list(c.values())
#print(a)
a.sort(reverse=True)
print(n-a[1])

### FIXED CODE ###

#%%
import collections

n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

l = []
for i in range(n):
    for j in range(n):
        tmp = str(x[i]-x[j]) + ' ' + str(y[i]-y[j])
        l.append(tmp)

c = collections.Counter(l)
a = list(c.values())
#print(a)
a.sort(reverse=True)


if n == 1:
    print(1)
else:
    print(n-a[1])
N, A, B = map(int, input().split())
F = A + B
C = N // F
D = N % C
E = A * C
if A == 0:
  print(0)
elif B == 0:
  print(A)
elif C == 0:
  if N < A:
    print(N)
  else:
    print(A)
else:
  if D < A:
    print(E + D)
  else:
    print(E + A)
  


### FIXED CODE ###

N, A, B = map(int, input().split())
C = N // (A + B) * A + N % (A + B)
D = N // (A + B) * A + A
if A == 0:
    print(0)
elif B == 0:
    print(N)
elif N % (A + B) > A:
    print(D)
else:
    print(C)
#1. input
n = int(input())
red_list = []
blue_list = []

for i in range(n):
    x, y = map(int, input().split())
    red_list.append([x, y])
for i in range(n):
    x, y = map(int, input().split())
    blue_list.append([x, y])

#2. search
#2.1 red:descending order in y
red_list.sort(key=lambda x:(x[1], x[0]), reverse=True)

#2.2 blue: ascending order
blue_list.sort(key=lambda x:(x[1], x[0]), reverse=False)

#2.3 search a blue point such as [x_r, y_r] < [x_b, y_b]
ans = 0
for red in red_list:
    for blue in blue_list:
        if (red[0]<blue[0]) and (red[1]<blue[1]):
            blue_list.remove(blue)
            ans += 1
            break


#3. print the result
print(ans)
logger.log(30, ans)

### FIXED CODE ###

n = int(input())
red_list = []
blue_list = []

for i in range(n):
    x, y = map(int, input().split())
    red_list.append([x, y])
for i in range(n):
    x, y = map(int, input().split())
    blue_list.append([x, y])

#2. search
#2.1 red:descending order in y
red_list.sort(key=lambda x:(x[1], x[0]), reverse=True)

#2.2 blue: ascending order
blue_list.sort(key=lambda x:(x[0], x[1]), reverse=False)

#2.3 search a blue point such as [x_r, y_r] < [x_b, y_b]
ans = 0
for red in red_list:
    for blue in blue_list:
        if (red[0]<blue[0]) and (red[1]<blue[1]):
            blue_list.remove(blue)
            ans += 1
            break

#3. print the result
print(ans)
a,b = int(input())
r = a * b
print(r)

### FIXED CODE ###

a,b = map(int, input().split())
r = a * b
print(r)
n = int(readline())
a = list(map(int,read().split()))
mod = 998244353

sum_a = sum(a)
dp = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rg = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rb = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r[0][0] = 1
tot = 0

for i in range(1,n+1):
    ai = a[i-1]
    tot += ai
    for j in range(tot+1):
        dp_rg[i][j] += dp_rg[i-1][j] + dp_r[i-1][j]
        dp_rb[i][j] += dp_rb[i-1][j] + dp_r[i-1][j]
        dp[i][j] += dp[i-1][j] * 2 + dp_rb[i-1][j] + dp_rg[i-1][j]

        if(j >= ai):
            dp_r[i][j] += dp_r[i-1][j-ai]
            dp_rg[i][j] += dp_rg[i-1][j-ai]
            dp_rb[i][j] += dp_rb[i-1][j-ai]
            dp[i][j] += dp[i-1][j-ai]
        dp_rg[i][j] %= mod
        dp_rb[i][j] %= mod
        dp[i][j] %= mod

r_over = sum(dp[-1][(1+sum_a)//2:]) % mod
ans = (pow(3,n,mod) - 3*pow(2,n,mod) + 3 - 3*r_over)%mod
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,read().split()))
mod = 998244353

sum_a = sum(a)
dp = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rg = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rb = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r[0][0] = 1
tot = 0

for i in range(1,n+1):
    ai = a[i-1]
    tot += ai
    for j in range(tot+1):
        dp_rg[i][j] += dp_rg[i-1][j] + dp_r[i-1][j]
        dp_rb[i][j] += dp_rb[i-1][j] + dp_r[i-1][j]
        dp[i][j] += dp[i-1][j] * 2 + dp_rb[i-1][j] + dp_rg[i-1][j]

        if(j >= ai):
            dp_r[i][j] += dp_r[i-1][j-ai]
            dp_rg[i][j] += dp_rg[i-1][j-ai]
            dp_rb[i][j] += dp_rb[i-1][j-ai]
            dp[i][j] += dp[i-1][j-ai]
        dp_rg[i][j] %= mod
        dp_rb[i][j] %= mod
        dp[i][j] %= mod

r_over = sum(dp[-1][(1+sum_a)//2:]) % mod
ans = (pow(3,n,mod) - 3*pow(2,n,mod) + 3 - 3*r_over)%mod
print(ans)
n=int(input())
a=sorted(list(map(int,input().split())))
ans=10**7
m=a[-1]
for i in range(len(a)-1):
    t=m%(a[i+1]-a[i])
    s=a[i+1]%a[i]
    if t!=0:
        ans=min(ans,t)
    if s!=0:
        ans=min(ans,s)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
ans=10**10
for i,j in zip(a,a[1:]):
    ans=min(ans,gcd(i,j))
print(ans)
a, b = map(int, input())
print([b+a,b-a][b%a>0])

### FIXED CODE ###

a, b = map(int, input().split())
print([b+a,b-a][b%a>0])
print (x*x*x)

### FIXED CODE ###

x = int(input())
print(x ** 3)
n = int(input())

int_cnt = 0
int_25 = [[0 for _ in range(10)] for _ in range(10)]
int_10 = [0 for _ in range(10)]
float_25 = [[0 for _ in range(11)] for _ in range(11)]
float_10 = [0 for _ in range(10)]
float22 = [0 for _ in range(10)]
float55 = [0 for _ in range(10)]

for _ in range(n):
    a = float(input())
    if a % 1 == 0:
        int_cnt += 1
        num = a
        cnt = 0
        while num % 10 == 0:
            cnt += 1
            num //= 10
        int_10[cnt] += 1
        num = a
        cnt2 = 0
        while num % 2 == 0:
            cnt2 += 1
            num //= 2
        num = a
        cnt5= 0
        while num % 5 == 0:
            cnt5 += 1
            num //= 5
        int_25[cnt2][cnt5] += 1
    else:
        a *= 10 ** 9
        a = int(a)
        num = a
        cnt = 9
        while num % 10 == 0:
            cnt -= 1
            num //= 10
        float_10[cnt] += 1
        num = a
        cnt = 9
        while num % 2 == 0:
            cnt -= 1
            num //= 2
        if cnt >= 0:
            cnt2 = cnt
        else:
            cnt2 = 0
            cnt = abs(cnt)
            cnt = min(cnt, 9)
            float22[cnt] += 1
        num = a
        cnt = 9
        while num % 5 == 0:
            cnt -= 1
            num //= 5
        if cnt >= 0:
            cnt5 = cnt
        else:
            cnt5 = 0
            cnt = abs(cnt)
            cnt = min(cnt, 9)
            float55[cnt] += 1
        float_25[cnt2][cnt5] += 1

ans = int_cnt * (int_cnt - 1) // 2

for i in range(10):
    for j in range(10):
        for k in range(i + 1):
            for l in range(j + 1):
                ans += int_25[i][j] * float_25[k][l]

for i in range(1, 10):
    for j in range(1, 10):
        ans += float22[i] * float55[j]


print(ans)



### FIXED CODE ###

n = int(input())

lst = [[0 for _ in range(25)] for _ in range(25)]
int_cnt = 0
for _ in range(n):
    a = input()
    if "." in a:
        pos = a.index(".")
        a1, a2 = a[:pos], a[pos + 1:]
        l = len(a2)
        a = a1 + a2
        a = int(a)
        a *= 10 ** (9 - l)
    else:
        a = int(a)
        int_cnt += 1
        a *= 10 ** 9
    t = 0
    while a % 2 == 0:
        t += 1
        a //= 2
    f = 0
    while a % 5 == 0:
        f += 1
        a //= 5
    t = min(t, 24)
    f = min(f, 24)
    lst[t][f] += 1


 
ans = 0
for i in range(25):
    for j in range(25):
        for k in range(25):
            for l in range(25):
                if i + j >= 18 and k + l >= 18:
                    if i == j and k == l:
                        tmp = lst[i][k]
                        ans += tmp * (tmp - 1)
                    else:
                        ans += lst[i][k] * lst[j][l]
print(ans // 2)
a,b=map(int,input().split())
alllist=[]
goukei=0
for i in range(a):
    tmplist=list(map(int,input().split()))
    alllist.append(tmplist)
    
sorted(alllist)
for i in range(a):
    goukei=alllist[a][1]+goukei
    if goukei>b:
        owari=alllist[a][0]
        break
    else:
        pass

print(owari)

### FIXED CODE ###

a,b=map(int,input().split())
alllist=[]
goukei=1
for i in range(a):
    tmplist=list(map(int,input().split()))
    alllist.append(tmplist)

alllist2=sorted(alllist)
for i in range(a):
    goukei=alllist2[i][1]+goukei
    if goukei>b:
        owari=alllist2[i][0]
        break
    else:
        pass

print(owari)
import numpy as np
N = int(input())
T,A = map(int,input().split(" "))
H =  list(map(lambda x:abs(T - float(x)*0.006 - A),input().split(" ")))
print(np.argmin(H)+1)


### FIXED CODE ###

X,Y = map(int,input().split(" "))
print(X + (Y//2))
print((lambda x: int((int(x[0]) + int(x[1])) / 2 + 0.999999999999999999999999999999))(input().split())print((lambda x: int(0.999999999999 + ((int(x[0]) + int(x[1])) / 2)))(input().split()))

### FIXED CODE ###

print((lambda x: int(0.999999999999 + ((int(x[0]) + int(x[1])) / 2)))(input().split()))
# -*- coding:utf-8 -*-
from operator import itemgetter
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(key=itemgetter(0),reverse=True)
s = []
b = []
a.append([0,0])
while (True):
    if a[-2][0]==0:break
    a.sort(key=itemgetter(1),reverse=True)
    a.sort(key=itemgetter(0),reverse=True)
    b=[]
    for i,p in enumerate(a[:-1]):
        if not p[0] == a[i+1][0]:
            q = p[0] - a[i+1][0]
            s.extend([p[1]]*(i+1)*q)
            for j in range(i):
                a[j][0] = a[i+1][0]
            a[i][0] = a[i+1][0]
            break
        else:
            pass
for i in xrange(1,int(n)+1):
    print(s.count(i))

### FIXED CODE ###

# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
min_a_i = float('inf')
for i,p in enumerate(a[:-1]):
    min_a_i = min(min_a_i, a[i][1])
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        s[min_a_i-1] += (i+1)*q

for t in s:
    print(t)
x = input()
st = [ 'Sunny' , 'Cloudy' , 'Rainy' ]
print(st[st.index(x) + 1 % 3])

### FIXED CODE ###

st = [ "Sunny" , "Cloudy" , "Rainy" ]
x = input()
s = st.index(x) + 1
if s <= 2 :
    print(st[s])
else :
    print(st[0])
# D - Friend Suggestions

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

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

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

        if x == y:
            return

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self, x, y):
        return self.root(x) == self.root(y)

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

N,M,K = map(int,input().split())
friend = UnionFind(N+1)
block = [1]*(N+1)
for _ in range(M):
    x,y = map(int,input().split())
    block[x] += 1
    block[y] += 1
    friend.union(x,y)
for _ in range(K):
    x,y = map(int,input().split())
    if friend.same(x,y):
        block[x] += 1
        block[y] += 1
ans = [friend.size(i)-block[i] for i in range(1,N+1)]
print(*ans)

### FIXED CODE ###

# D - Friend Suggestions

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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 same(self, x, y):
        return self.root(x) == self.root(y)

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

N,M,K = map(int,input().split())
friend = UnionFind(N+1)
block = [1]*(N+1)
for _ in range(M):
    x,y = map(int,input().split())
    block[x] += 1
    block[y] += 1
    friend.union(x,y)
for _ in range(K):
    x,y = map(int,input().split())
    if friend.same(x,y):
        block[x] += 1
        block[y] += 1
ans = [friend.size(i)-block[i] for i in range(1,N+1)]
print(*ans)
x=int(input())
i=x//500
a=(x-i)//5
sum=i*1000+a*5
print sum


### FIXED CODE ###

x=int(input())
i=x//500
a=(x-i*500)//5
print(i*1000+a*5)
N = int(input())
S = str(input())
K = int(input())
SS = list(S)
for i in range(N):
  if(SS[i]==SS[K]):
    None
  else:
    SS[i] = "*"
SSS = str(SS)
print(SSS)

### FIXED CODE ###

N = int(input())
S = str(input())
K = int(input())
H = ""
for i in range(N):
  if(S[i]==S[K-1]):
    H+=S[i]
  else:
    H+="*"
print(H)