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

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    ret = float('inf')
    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                cri = S[idxes[i]:idxes[i+1], l:r].sum()
                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
from itertools import combinations as combs

H,W,K = list(map(int, input().split()))
arr = []
for i in range(H):
  arr.append(list(map(int, list(input()))))

def cut_sum(arr, x1, x2, y):
  ret = 0
  for i in range(x1, x2):
    ret += arr[i][y]
  return ret

row_idxes = list(range(1,H))
min_val = float('inf')

for n_rows in range(H):
  for row_set in combs(row_idxes, n_rows):
    count = len(row_set)
    row_lines = [0] + list(row_set)+ [H]
    col1, col2 = 0, 1
    sums = [0] * (len(row_lines) - 1)
    while col2 <= W:
      row1 = 0
      for box, row2 in enumerate(row_lines[1:]):
        sums[box] += cut_sum(arr, row1, row2, col2-1)
        if sums[box] > K:
          if (col2 - col1) == 1:
            count = float('inf')
            break
          count += 1
          col1 = col2 - 1
          col2 -= 1
          sums = [0] * (len(row_lines) - 1)
          break
        row1 = row2
      if count >= min_val:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)
### BUGGY CODE ###

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

blacks = []
for h in range(H):
     for w in range(W):
         if A[h][w] == "#":
             blacks.append((h, w))

max_dist = 0
for h in range(H):
    for w in range(W):
        min_d = H+W
        for (i, j) in blacks:
            cm = abs(h - i) + abs(w - j)
            if cm < min_d:
                min_d = cm
        if min_d > max_dist:
            max_dist = min_d

print(max_dist)

### FIXED CODE ###

# 参考

import numpy

H, W = map(int, input().split())
values = [None] * H

for y in range(H):
    values[y] = [0 if v == "#" else H + W for v in input()]
values = numpy.array(values)

for x in range(W - 1):
    values[:, x + 1] = numpy.minimum(values[:, x] + 1, values[:, x + 1])

for x in range(W - 1, 0, -1):
    values[:, x - 1] = numpy.minimum(values[:, x] + 1, values[:, x - 1])

for y in range(H - 1):
    values[y + 1, :] = numpy.minimum(values[y, :] + 1, values[y + 1, :])

for y in range(H - 1, 0, -1):
    values[y - 1, :] = numpy.minimum(values[y, :] + 1, values[y - 1, :])

print(numpy.max(values))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
cum_sum = [0] + [sum(A[:i + 1]) for i in range(N)]

ans = float("inf")


def get_diff(left, center, right):
    return abs((cum_sum[center] - cum_sum[left]) - (cum_sum[right] - cum_sum[center]))


l_point = 1
r_point = 3

for C in range(2, N):
    while l_point + 1 < C and get_diff(0, l_point, C) > get_diff(0, l_point + 1, C):
        l_point += 1
    while r_point + 1 < N and get_diff(C, r_point, N) > get_diff(C, r_point + 1, N):
        r_point += 1

    pqrs = [cum_sum[l_point], cum_sum[C] - cum_sum[l_point], cum_sum[r_point] - cum_sum[C], cum_sum[N] - cum_sum[r_point]]
    ans = min(ans, max(pqrs) - min(pqrs))

print(ans)


### FIXED CODE ###

import sys
 
n = int(input())
a = list(map(int, input().split()))
aa = [0]
for i in range(n):
    aa.append(aa[i] + a[i])
 
ans = sys.maxsize
 
def getdiff(left, center, right):
    return abs((aa[center] - aa[left]) - (aa[right] - aa[center]))
 
L = 1
R = 3
 
for C in range(2, n):
    while L + 1 < C and getdiff(0, L, C) > getdiff(0, L + 1, C):
        L += 1
    while R + 1 < n and getdiff(C, R, n) > getdiff(C, R + 1, n):
        R += 1
    pqrs = [aa[L], aa[C] - aa[L], aa[R] - aa[C], aa[n] - aa[R]]
    pqrs.sort()
    ans = min(ans, pqrs[3] - pqrs[0])
 
print(ans)
### BUGGY CODE ###

import numpy as np

n,k= map(int,input().split())
a = list(map(int,input().split()))
target = a[0:k]
p = a[0]
for i in range(k-1):
    p *= a[i+1]
# print(p)
for i in range(n-k):
    ans = (p // a[i]) * a[i+k]
    # print(ans)
    if ans > p:
        print("Yes")
    else:
        print("No")
    p = ans


### FIXED CODE ###

import numpy as np

n,k= map(int,input().split())
a = list(map(int,input().split()))
target = a[0:k]
p = sum(target)
for i in range(n-k):
    ans = p - a[i] + a[i+k]
    # print(ans)
    if ans > p:
        print("Yes")
    else:
        print("No")
    p = ans
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result=1
for i in (a):
    result *= i
 # Multiply elements one by one
if result> (10**18):
     print("-1")
else:
     print(result)


### FIXED CODE ###

# we collect the input A1 upto An.
# limit cannot exceed 10**18
# if N = 0 then ans = 0
# in N is in range then compute ans * A[n]
# else if  ans is greater than limit then display 1
# finally if length equal 1 then display -1
N = int(input())
ans = 1
limit = 10 ** 18
length = 0

A = list(map(int, input().split()))

A0 = set(A)
if 0 in A0:
    ans = 0
else:
    pass

for n in range(N):
    ans = ans * A[n]
    if ans == 0:
        break
    elif ans > limit:
        length = 1
        break
    else:
        pass

if length == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

value = 0
N = int(input())
L = list(map(int,input().split()))
L = sorted(L)
a_plus_b = [] 
for i in range(1,N-1):
  for j in range(i):
    a_plus_b.append(L[j]+L[i])

for i in range(2,N):
  for j in range(i*(i-1)//2):
    if L[i] < a_plus_b[j]:
      value += 1
print(value)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)

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

from collections import deque

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


def successors(x, y):
    locations = []
    # 下に行けるかの判定
    if (x + 1 < H) and (maze[x + 1][y] != '#'):
        locations.append((x + 1, y))
    # 上に行けるかの判定
    if (x - 1 >= 0) and (maze[x - 1][y] != '#'):
        locations.append((x - 1, y))
    # 右に行けるかの判定
    if (y + 1 < W) and (maze[x][y + 1] != '#'):
        locations.append((x, y + 1))
    # 左に行けるかの判定
    if (y - 1 >= 0) and (maze[x][y - 1] != '#'):
        locations.append((x, y - 1))
    return locations


def bfs(initial, successors):
    # goal判定はなく、一番遠いところで返す
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}

    while len(frontier):
        current_node = frontier.popleft()
        current_state = current_node[0]
        for child in successors(*current_state):
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.append((child, current_node))
    return current_node


def node_to_path_count(node):
    counter = 0
    while node[1] is not None:
        counter += 1
        node = node[1]
    return counter


ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == '.':
            solution = bfs((x, y), successors)
            counter = node_to_path_count(solution)
            if ans < counter:
                ans = counter

print(ans)

### FIXED CODE ###

from collections import deque

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


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x, y = current_node
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < W:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        solution = bfs((i, j))
        if ans < solution:
            ans = solution

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

n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
ans = 0
b = []
for k in range(n):
    if k == 0:
        b = a.copy()
    else:
        for i in range(n):
            b[i] = min(a[(i-k)%n],b[i])
    cost = k*x+sum(b)
    if k == 0:
        ans = cost
    else:
        ans = min(ans,cost)
        if ans != cost:
            break
    if ans < (k+1)*x:
        break
print(ans)

### FIXED CODE ###

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n // b) + n % b

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    for i in range(2, n+1):
        if f(i, n) == s:
            print(i)
            exit()
    print(-1)


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
・参考：http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
　　　　https://www.youtube.com/watch?v=LzxPxJ-cSHk
・b <= √nは愚直に当たっていく。
・b > √nは、b^2 > nなので、b進数で2桁以下になる。
　例) 10^2は10進数で100、100 > n → nは99以下
　その2桁の数字はn = p*b + qと表せる。
　例) 67 = 6*10 + 7
　今回の問題の条件から、s = p + q
　n = p*b + q
　s = p + q
　上記2つの式から、連立方程式でqを消すと、
　n-s = p*b - p
　と表せる。
　pはb以上なら桁が上がってしまうので p < b
　p < b から p*p < p*b なので、p*b > p^2
　よって、n = p*b + q >= p*b > p^2
　n > p^2 なので、√n > p
　つまりpについて√nまでを全探索すればOK。
　n-s = p*b - p をbについての形に変形すればbが出せる。
　b = (n-s)/p + 1
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n // b) + n % b

n = INT()
s = INT()

if s > n:
    print(-1)
elif s == n:
    print(n+1)
elif ceil(n/2) < s < n:
    print(-1)
else:
    # b <= √n の全探索
    for b in range(2, int(sqrt(n))+2):
        if f(b, n) == s:
            print(b)
            exit()
    # b > √n について、式を元に探す
    # pが大きい程bが小さいので、このループは逆順で回す
    for p in range(int(sqrt(n))+2, 0, -1):
        # 整数にならないものは除外
        if (n-s)%p: continue
        b = (n-s)//p + 1
        if f(b, n) == s:
            print(b)
            exit()
    # 見つからなかった
    print(-1)
### BUGGY CODE ###

N, M=map(int, input().split())
A,B=[],[]
A_t,B_t=0,0
s = 0
r = 0
for i in range(N):
    A_t, B_t = map(int,input().split())
    A.append(A_t)
    B.append(B_t)
#自力でsort関数を作ればいいのでは？
for i in range(N-1):
    for j in range(N-i-1):
        if A[j] > A[j+1]:
            A[j], A[j+1] = A[j+1], A[j]
            B[j], B[j + 1] = B[j + 1], B[j]
for j in range(N):
    if M == 0:
        break
    elif M < B[j]:
        s += A[j] * M
        #print(B[j],M)
        break
    else:
        s += A[j] * B[j]
        M -= B[j]
        #print(s,M,A[j],B[j])
print(s)


### FIXED CODE ###

N, M = map(int,input().split())
A = []
B = []
ta = 0
tb = 0
# for i in range(N):
#     ta, tb = map(int, input().split())
#     A.append(ta)
#     B.append(tb)
# print(A,B)
L = [list(map(int,input().split())) for i in range(N)]
#print(L)
L.sort(key=lambda x: x[0])
#print(L)
c = 0
for i in range(N):
    if M <= L[i][1]:
        print(c + L[i][0] * M)
        exit()
    else:
        M -= L[i][1]
        c += L[i][0] * L[i][1]
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def abc161e(n, k, c, s):
    num_cluster_f = 0
    start = []
    cursor = 0
    while cursor < n:
        if s[cursor] == "x":
            cursor += 1
            continue
        else:
            num_cluster_f += 1
            start.append(cursor)
            cursor += c+1

    if k < num_cluster_f:
        return []

    num_cluster_b = 0
    end = []
    cursor = n-1

    while 0 <= cursor:
        if s[cursor] == "x":
            cursor -= 1
            continue
        else:
            num_cluster_b += 1
            end.insert(0, cursor)
            cursor -= c+1

    if k < num_cluster_b:
        return []

    ans = []
    if num_cluster_b < num_cluster_f:
        num_cluster_f = num_cluster_b
    for s, e in zip(start, end):
        if s == e:
            ans.append(s+1)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n, k, c = map(int, input().split(" "))
    s = input()
    
    ans = abc161e(n, k, c, s)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing


### FIXED CODE ###

# -*- coding: utf-8 -*-

def abc161e(n, k, c, s):
    num_cluster_f = 0
    start = []
    cursor = 0
    while cursor < n:
        if s[cursor] == "x":
            cursor += 1
            continue
        else:
            num_cluster_f += 1
            start.append(cursor)
            cursor += c+1

    if k < num_cluster_f:
        return []

    num_cluster_b = 0
    end = []
    cursor = n-1

    while 0 <= cursor:
        if s[cursor] == "x":
            cursor -= 1
            continue
        else:
            num_cluster_b += 1
            end.append(cursor)
            cursor -= c+1

    if k < num_cluster_b:
        return []

    ans = []
    if num_cluster_b < num_cluster_f:
        num_cluster_f = num_cluster_b
    for s, e in zip(start, end[::-1]):
        if s == e:
            ans.append(s+1)

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n, k, c = map(int, input().split(" "))
    s = input()
    
    ans = abc161e(n, k, c, s)
    
    # output
    for a in ans:
        print(a)
# else:
    # do nothing
### BUGGY CODE ###

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

def g(m):
  if data[0][0] == '.':
    a = 0
  else:
    a = 1
    
  for i in range(1,m,1):
    if data[0][i] == '.':
      continue
    elif data[0][i] == '#' and data[0][i-1] == '.':
      a += 1
    else:
      continue
  return a

def h(n):
  if data[0][0] == '.':
    a = 0
  else:
    a = 1
    
  for i in range(1,n,1):
    if data[i][0] == '.':
      continue
    elif data[i][0] == '#' and data[i-1][0] == '.':
      a += 1
    else:
      continue
  return a
  
def f(n,m):
  if n == 1:
    return g(m)
  elif m == 1:
    return h(n)
  else:
    if data[n-1][m-1] == '.':
      return min(f(n-1,m),f(n,m-1))
    elif data[n-2][m-1] == '.':
      if data[n-1][m-2] == '.':
        return min(f(n-1,m)+1,f(n,m-1)+1)
      else:
        return min(f(n-1,m)+1,f(n,m-1))
    else:
      if data[n-1][m-2] == '.':
        return min(f(n-1,m),f(n,m-1)+1)
      else:
        return min(f(n-1,m),f(n,m-1))
      
print(f(H,W))

### FIXED CODE ###

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


def g(m):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, m, 1):
        if data[0][i] == '.':
            continue
        elif data[0][i] == '#' and data[0][i - 1] == '.':
            a += 1
        else:
            continue
    return a


def h(n):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, n, 1):
        if data[i][0] == '.':
            continue
        elif data[i][0] == '#' and data[i - 1][0] == '.':
            a += 1
        else:
            continue
    return a

A = [0] + [g(i) for i in range(1,W+1)]
B = [0] + [h(i) for i in range(1,H+1)]
C = [[0]*(W+1) for i in range(H+1)]

for n in range(1,H+1):
    for m in range(1,W+1):
        if n == 1:
            C[n][m] = A[m]
        elif m == 1:
            C[n][m] = B[n]
        else:
            if data[n - 1][m - 1] == '.':
                C[n][m] = min(C[n - 1][m], C[n][m - 1])
            elif data[n - 2][m - 1] == '.':
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m] + 1, C[n][m - 1] + 1)
                else:
                    C[n][m] =  min(C[n - 1][m] + 1, C[n][m - 1])
            else:
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m], C[n][m - 1] + 1)
                else:
                    C[n][m] = min(C[n - 1][m], C[n][m - 1])


print(C[H][W])
### BUGGY CODE ###

import sys

info = input().split(" ")
N = int(info[0])
K = int(info[1])
Q = int(info[2])
  
point = [K]*N
  
for i in range(1, Q+1):
  person = int(input())
  for n in range(N):
    if person != n+1:
      point[n] = point[n] - 1
      
  
for p in point:
  if p <= 0:
    print("No")
  else:
    print("Yes")


### FIXED CODE ###

import sys

info = input().split(" ")
N = int(info[0])
K = int(info[1])
Q = int(info[2])
  
ns = []
for i in range(N):
  ns.append(K - Q)

for i in range(Q):
  s = int(input())
  s = s - 1
  ns[s] = ns[s] + 1
      
  
for p in ns:
  if p <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

n = int(input())
xy = []
for i in range(n):
	xy.append(list(map(int, input().split())))

a = []
num = [i for i in range(n)]
num2 = num.reverse()
m = "".join(map(str, num))
for i in range(int(m)+1):
	s = []
	for l in range(len(str(i))):
		s.append(str(i)[l])
	ii = ['0' for j in range(n-len(str(i)))] + s
	for l in range(len(ii)):
		ii[l] = int(ii[l])
	if set(ii) == set(num):
		a.append(ii)

dt = []
for i in range(len(a)):
	d = []
	for j in range(n-1):
		d.append(((xy[int(a[i][j])][0]-xy[int(a[i][j+1])][0])**2+(xy[int(a[i][j])][1]-xy[int(a[i][j+1])][1])**2)**(1/2))
	dt.append(sum(d))
print(sum(dt)/len(dt))

### FIXED CODE ###

import math
n = int(input())
xy = []
for i in range(n):
	xy.append(list(map(int, input().split())))
d = []
for i in range(n-1):
	for j in range(i, n):
		d.append(((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**(1/2))
print(2*sum(d)/n)
### BUGGY CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(s-i+1):
        if s-i-j > k:
            continue
        elif j > k:
            break
        z = s - i - j
        if 0<= z <= k:
            n += 1
print(n)


### FIXED CODE ###

k, s = map(int, input().split())
n = 0
for i in range(k + 1):
    if (s-i)/2 > k:
        continue
    elif i > s:
        break
    for j in range(k+1):
        z = s - i - j
        if 0<= z <= k:
            n += 1
print(n)
### BUGGY CODE ###

def BFS(x):
  cnt=0
  v=deque([x])
  zu=[ -1 for _ in range(N)] #訪問済みリスト
  k=0
  zu[x]=k
  
  while len(v)>0:
    a=v.popleft()
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        if zu[i]>1 and (i not in bl[x]):
          cnt +=1            
  return cnt

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ [] for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].append(D[k]-1)
  bl[D[k]-1].append(C[k]-1)

ans=[]  
for i in range(N):
  ans.append(BFS(i))
print(*ans)

### FIXED CODE ###

def BFS(x):
  cnt=1
  v=deque([x])
  k=0
  zu[x]=k
  lis=[x]
  roots[x]=x
  
  while len(v)>0:
    a=v.popleft()
    roots[a]=x
    for i in fr[a]:
      if zu[i]==-1:
        zu[i]=zu[a]+1
        v.append(i)
        cnt += 1
        lis.append(i)

          
  return lis

##############################

from collections import deque
N,M,K=map(int,input().split())
A=[0]*M
B=[0]*M
C=[0]*K
D=[0]*K
fr=[ [] for _ in range(N)]
bl=[ set() for _ in range(N)]
zu=[ -1 for _ in range(N)] #訪問済みリスト
roots= [ -1 for _ in range(N)]

for i in range(M):
  A[i],B[i]= map(int,input().split())
  fr[A[i]-1].append(B[i]-1)
  fr[B[i]-1].append(A[i]-1)
for k in range(K):
  C[k],D[k]= map(int,input().split())
  bl[C[k]-1].add(D[k]-1)
  bl[D[k]-1].add(C[k]-1)
fr_set= [set(fr[i]) for i in range(N)]
    
size=[0]*N
pena=[0]*N
for i in range(N):
  if zu[i]==-1:
    kumi=BFS(i) #リスト
    for k in range(len(kumi)):
      size[kumi[k]]=len(kumi)
      
      
ans=[0 for _ in range(N)]      
for i in range(N):
  ans[i]= size[i]-1 - len(fr[i])
  for j in bl[i]:
    if roots[j]==roots[i]:
      ans[i] -= 1      
      
print(*ans)