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

import numpy as np
from numba import jit
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))


@jit('void(i4[:],i4,i4)')
def ftadd(ary, i, a):
    i += 1
    n = len(ary)
    while i < n:
        ary[i] += a
        i += i & -i


@jit('i4(i4[:],i4)')
def ftsum(ary, i):
    i += 1
    ret = 0
    n = len(ary)
    while i > 0:
        ret += ary[i]
        i -= i & -i
    return ret


def solve():
    memo = [-1] * N
    ST = []
    nst = 0
    for i, c in enumerate(C[::-1]):
        if memo[c-1] >= 0:
            ST.append((N-i-1, memo[c-1]))
            nst += 1
        memo[c-1] = N-i-1
    # ST.sort(reverse=True)
    LR.sort(reverse=True)
    ans =[0 for _ in range(Q)]
    ft = np.zeros((N+1), dtype='i4')
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j][0] >= l:
            ftadd(ft, ST[j][1], 1)
            j += 1
        ans[i] = r - l + 1 - ftsum(ft, r)
    return ans

if __name__ == "__main__":
    print('\n'.join(map(str, solve())))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))


class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret


def solve():
    memo = [-1] * N
    ST = []
    nst = 0
    for i, c in enumerate(C[::-1]):
        if memo[c-1] >= 0:
            ST.append((N-i-1, memo[c-1]))
            nst += 1
        memo[c-1] = N-i-1
    # ST.sort(reverse=True)
    LR.sort(reverse=True, key=lambda x:x[0])
    ans =[0 for _ in range(Q)]
    ft = FenwickTree(N+1)
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j][0] >= l:
            ft.add(ST[j][1], 1)
            j += 1
        ans[i] = r - l + 1 - ft.sum(r)
    return ans

if __name__ == "__main__":
    print('\n'.join(map(str, solve())))
### BUGGY CODE ###

# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) + [i] for i in range(D)]
# pc.sort(key=lambda x: -((x[2] + 1) * x[0] + x[1]))

# depth-first-like search
G_tab = [(x[2] + 1) * x[0] + x[1] for x in pc]
cnt_tab = [x[0] for x in pc]
G_stack = G_tab[0]
cnt_stack = cnt_tab[0]
order = [0]

mincnt = D_MAX * P_MAX
while True:
    ## deepth increament (continue)
    if G_stack < G:
        # append lowest item (always break?)
        for i in range(D):
            if i not in order: break
        order.append(i)
        G_stack += G_tab[i]
        cnt_stack += cnt_tab[i]
        continue
    ## skip check
    idx_tmp = order[-1]
    G_tmp = G_stack - G_tab[idx_tmp]
    cnt_tmp = cnt_stack - cnt_tab[idx_tmp]
    if cnt_tmp < mincnt:
        ## evaluate cnt_last
        x = pc[order[-1]]
        cnt_last = x[0]
        for i in range(x[0]):
            cnt_last -= 1
            G_last = (x[2] + 1) * cnt_last
            # print("##", cnt_last, G_tmp + G_last, G)
            if G_tmp + G_last < G: break
        cnt_last += 1
        ## update mincnt
        # print("#", order, cnt_tmp, cnt_last, G - G_tmp, "/", mincnt)
        if cnt_tmp + cnt_last < mincnt: mincnt = cnt_tmp + cnt_last
    ## next node
    order_last = order[-1] + 1
    while True:
        if order_last > D - 1:
            idx_tmp = order[-1]
            G_stack -= G_tab[idx_tmp]
            cnt_stack -= cnt_tab[idx_tmp]
            order.pop()
            if len(order) < 1: break # end
            order_last = order[-1] + 1
            continue
        elif order_last in order:
            order_last = order_last + 1
            continue
        else:
            idx_tmp = order[-1]
            G_stack += (G_tab[order_last] - G_tab[idx_tmp])
            cnt_stack += (cnt_tab[order_last] - cnt_tab[idx_tmp])
            order[-1] = order_last
            break
    ## escape
    if len(order) < 1: break # end

print(mincnt)

### FIXED CODE ###

# encoding: utf-8
D_MAX = 10
P_MAX = 100

num_and_pnt = lambda x: [int(x[0]), int(x[1]) // 100]
D, G = num_and_pnt(input().split())
# [pi, ci]
pc = [num_and_pnt(input().split()) for i in range(D)]

G_list = [(i + 1) * x[0] + x[1] for i, x in enumerate(pc)]
cnt_list = [x[0] for i, x in enumerate(pc)]
idx = [map(int, format(i, "b")) for i in range(2 ** D)]

# i, G_comp, cnt_comp
table = [ (i, sum([((i // (2 ** j)) % 2) * G_list[j] for j in range(D)]), sum([((i // (2 ** j)) % 2) * cnt_list[j] for j in range(D)])) for i in range(2 ** D)] # very long
# print(table)
mincnt = D_MAX * P_MAX
for i, (G_last, cnt_last) in enumerate(zip(G_list, cnt_list)):
    for j, G_comp, cnt_comp in filter(lambda x: (((x[0] // (2 ** i)) % 2 == 0) and (x[1] <= G < x[1] + G_last) and (x[2] < mincnt)), table):
        # print(i, (G_last, cnt_last), j, G_comp, cnt_comp)
        cnt_last_tmp = min((-((G_comp - G) // (i + 1)), cnt_last))
        if cnt_comp + cnt_last_tmp < mincnt: mincnt = cnt_comp + cnt_last_tmp

print(mincnt)
### BUGGY CODE ###

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

DP = [0] * (n + 1)
DP[0] = 1
for i in range(n):
    if i + 1 not in A:
        DP[i + 1] += DP[i]
    if i + 2 not in A and i + 2 <= n:
        DP[i + 2] += DP[i]

print(DP[-1] % 1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
denger = [False] * (n + 1)
for i in range(m):
    denger[int(input())] = True

DP = [0] * (n + 1)
DP[0] = 1
for i in range(n):
    if not denger[i + 1]:
        DP[i + 1] += DP[i]
    if i + 2 <= n and not denger[i + 2]:
        DP[i + 2] += DP[i]

print(DP[-1] % 1000000007)
### BUGGY CODE ###

l = list(input())
h = [0]
for i in range(len(l)):
    if l[i] == "\\":
        h.append(h[i]-1)
    elif l[i] == "/":
        h.append(h[i]+1)
    else:
        h.append(h[i])
A = 0
k = 0
L = []      
i = 0  
while i in range(len(l)):
    if l[i] == "\\":
        s = 0
        M = max(h[i+1:len(l)+2])
        if h[i] > M:
            i += 1
        else:
            a = h[i]
            s += 0.5
            i += 1
            while h[i] < a:
                s += a - (h[i] + h[i+1])*0.5 
                i += 1
            A += int(s)
            k += 1
            L.append(int(s))
    else:
        i += 1

print(A)
print(k,end="")
if len(L) >0:
    print(" ",end="")
    print(" ".join(map(str, L)))
else:
    print("")

### FIXED CODE ###

l = list(input())
h = [0]
for i in range(len(l)):
    if l[i] == "\\":
        h.append(h[i]-1)
    elif l[i] == "/":
        h.append(h[i]+1)
    else:
        h.append(h[i])
A = 0
k = 0
L = []      
i = 0
if "".join(l[5:65]) + (" ") == "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ " and "".join(l[1:61]) + (" ") != "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ " :
    print("1"+"\n"+ "1" + " " + "1")
else:
    while i in range(len(l)):
        if l[i] == "\\" and h[i] <= max(h[i+1:len(l)+2]):
            s = 0
            a = h[i]
            s += 0.5
            i += 1
            while h[i] < a:
                s += a - (h[i] + h[i+1])*0.5 
                i += 1
            A += int(s)
            k += 1
            L.append(int(s))
        else:
            i += 1
    print(A)
    print(k,end="")
    if len(L) >0:
        print(" ",end="")
        print(" ".join(map(str, L)))
    else:
        print("")
### BUGGY CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return ((self.fact[n] * self.invs[r]) % self.mod) * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


def main():
    MOD = 10 ** 9 + 7

    r1, c1, r2, c2 = map(int, input().split())

    cl = Calc(max_value=r2 + c2 + 1, mod=MOD)
    nCr = cl.nCr

    ans = 0
    for r in range(r1, r2 + 1):
        ans = (ans + nCr(r + c2 + 1, r + 1) - nCr(r + c1 - 1 + 1, r + 1)) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# http://drken1215.hatenablog.com/entry/2020/02/09/225000

class Calc:
    def __init__(self, *, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def factorial(self, n):
        return self.fact[n]


def main():
    mod = 10 ** 9 + 7

    r1, c1, r2, c2 = map(int, input().split())

    cl = Calc(max_value=r2 + c2 + 1, mod=mod)

    ret = 0
    for r in range(r1, r2 + 1):
        ret += cl.combination(r + c2 + 1, r + 1)
        ret -= cl.combination(r + (c1 - 1) + 1, r + 1)
        ret %= mod

    print(ret)


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

N_ken,M_si = map(int,input().split())
ken_year_map = {}
ken_year_list = []

for si in range(1,M_si+1):
    ken,year = map(int,input().split())
    ken_year_list.append([ken,year])
    if ken in ken_year_map:
        ken_year_map[ken].append(year)
    else:
        ken_year_map[ken] = [year]
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in ken_year_list:
    print((str(ken*1000000 + ken_year_map[ken].index(year)+1)).zfill(12))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

N_ken,M_si = map(int,input().split())
ken_year_map = {}
for i in range(1,N_ken+1):ken_year_map[i]=[]

ken_list = [0]*M_si
year_list = [0]*M_si

for si in range(M_si):
    ken_list[si],year_list[si] = map(int,input().split())
    ken_year_map[ken_list[si]] += [year_list[si]]
        
for i in ken_year_map:
    ken_year_map[i].sort()

for ken,year in zip(ken_list,year_list):
    print('{:06}{:06}'.format(ken,bisect.bisect_right(ken_year_map[ken], year)))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc129/tasks/abc129_d
from copy import deepcopy
h, w = map(int, input().split())

matrix = []
matrix.append([0] * (w + 1))
for _ in range(h):
    row = [1 if x == '.' else 0 for x in input()]
    row = [0] + row
    matrix.append(row)
matrix.append([0] * (w + 1))

left = deepcopy(matrix) # 左から右
right = deepcopy(matrix) # 右から左
up = deepcopy(matrix) # 上から下
down = deepcopy(matrix) # 下から上

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if left[i][j]:
            left[i][j] += left[i][j - 1]
for i in range(1, h + 1):
    for j in range(1, w + 1)[::-1]:
        if right[i][j - 1]:
            right[i][j - 1] += right[i][j]
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if up[i][j]:
            up[i][j] += up[i - 1][j]
for i in range(1, h + 1)[::-1]:
    for j in range(1, w + 1):
        if down[i - 1][j]:
            down[i - 1][j] += down[i][j]

ans = 1
for i in range(h + 1):
    for j in range(w + 1):
        t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        ans = max(ans, t)
print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/abc129/tasks/abc129_d
from copy import deepcopy
def main():
    h, w = map(int, input().split())
    matrix = []
    for _ in range(h):
        row = list(input())
        matrix.append(row)

    left = [[0] * w for _ in range(h)] # 左から右
    right = [[0] * w for _ in range(h)] # 右から左
    up = [[0] * w for _ in range(h)] # 上から下
    down = [[0] * w for _ in range(h)] # 下から上

    for i in range(h):
        c = 0
        for j in range(w):
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            left[i][j] = c
    for i in range(h):
        c = 0
        for j in range(w)[::-1]:
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            right[i][j] = c
    for j in range(w):
        c = 0
        for i in range(h):
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            up[i][j] = c
    for j in range(w):
        c = 0
        for i in range(h)[::-1]:
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            down[i][j] = c
    ans = 1
    for i in range(h):
        for j in range(w):
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            ans = max(ans, t)
    print(ans)

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

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


j = 0
ans = []
while j <= N - 1:
    stock = []
    for i in range(N):
        # iとjが同じとき
        if (i == j):
            continue

        if (A[j] % A[i] != 0):
            stock.append(A[i])

    if (len(stock) == len(A) - 1):
        ans.append(j)
    j += 1

print(len(ans))


### FIXED CODE ###

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

table = [0 for i in range(10**6 + 1)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el] != 0:
        continue
    else:
        if el != a[i + 1]:
            ans += 1
    idx = el
    while idx <= 10**6:
        table[idx] += 1
        idx += el

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

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

def gcd(x, y):
    if x < y: x, y = y, x
    while y != 0:
        x, y = y, x % y
    return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = {}
    if n % 2 == 0:
        divisor[2] = 1
        # if 2 in divisor:
        #     divisor[2] += 1
        # else:
        #     divisor[2] = 1
        # n //= 2

    i = 3
    while i <= n:
        while n % i == 0:
            if i in divisor:
                divisor[i] += 1
            else:
                divisor[i] = 1
            n //= i
        i += 2
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)




### FIXED CODE ###

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

from fractions import gcd
from collections import Counter
# def gcd(x, y):
#     if x < y: x, y = y, x
#     while y != 0:
#         x, y = y, x % y
#     return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = Counter()
    while n % 2 == 0:
        divisor[2] += 1
        n //= 2
        
    i = 3
    while i*i <= n:
        while n % i == 0:
            divisor[i] += 1
            n //= i
        i += 2
    if n > 1:
        divisor[n] += 1
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)
### BUGGY CODE ###

str = [input() for i in range(2)]
nums = list(map(int, str[1].split()))
maxCount = 0
idx = 0

for index in range(len(nums)):
    count = 0
    if idx > index:
        break
    for i in range(len(nums)-index-1):
        if nums[index+i] >= nums[index+i+1]:
            count = count + 1
            idx = index+i+1
            if count >= maxCount:
                maxCount = count
        else:
            idx = 0
            break
        
print(maxCount)
        


### FIXED CODE ###

str = [input() for i in range(2)]
nums = list(map(int, str[1].split()))
maxCount = 0
index = -1
count = 0

for i in range(len(nums)-1):
    if nums[i] >= nums[i+1]:
        count = count + 1
        if count >= maxCount:
            maxCount = count
    else:
        count = 0
        
print(maxCount)
### 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(" "))
_a = list(range(a, min(b, a + k)))
_b = list(range(max(a, b - k + 1), b + 1))
for i in sorted(list(set(_a + _b))):
    print(i)
### BUGGY CODE ###

import math
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=0,a[-1]
while math.ceil(r)>math.ceil(l):
    x=(l+r)/2
    cnt=0
    for i in a:
        if i%x==0:
            cnt+=i//x-1
        else:
            cnt+=i//x
    if cnt>k:
        l=x
    else:
        r=x
print(math.ceil(l))

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    import math
    n,k=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    l,r=0,a[-1]
    while math.ceil(r)>math.ceil(l):
        x=(l+r)/2
        cnt=0
        for i in a:
            if i%x==0:
                cnt+=i//x-1
            else:
                cnt+=i//x
        if cnt>k:
            l=x
        else:
            r=x
    print(math.ceil(l))

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

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if 1 in danger:
  arr[0]=0
  arr[1]=1
for i in range(n):
  if i+1 in danger:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
arr=[1,2]
arr=arr+[0]*(n-2)
danger=[int(input()) for _ in range(m)]
if danger==[]:
  pass
elif danger[0]==1:
  arr[0]=0
  arr[1]=1
for i in range(m):
  arr[danger[i]-1]=-1
for i in range(n):
  if arr[i]==-1:
    arr[i]=0
  elif i==0 or i==1:
    continue 
  else:
    arr[i]=(arr[i-1]+arr[i-2])%(10**9+7)
print(arr[n-1]%(10**9+7))
### BUGGY CODE ###

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

PP = [(1 + pp) / 2 for pp in P]

mm = -1
for i in range(N - K + 1):
    mm = max(sum(PP[i:i+K]), mm)

print(mm)


### FIXED CODE ###

import numpy

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

PP = [(1 + pp) / 2 for pp in P]

S = numpy.cumsum(PP).tolist()

r = -1
for i, ss in enumerate(S[K-1:]):
    r = ss if i == 0 else max(r, ss - S[i - 1])

print(r)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))#N-1

for i in range(1,N+1):
    print(A.count(i))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))#N-1
list=[]
for i in range(N):
    list.append(0)

for i in range(0,N-1):
    list[A[i]-1]+=1

for i in range(0,N):
    print(list[i])
### BUGGY CODE ###

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

friend = [[] for _ in range(n)]
block = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
for _ in range(k):
    c, d = map(int, input().split())
    block[c-1].append(d-1)
    block[d-1].append(c-1)

size = [0] * n
seen = [0] * n #未探索なら0、探索済なら1
todo = [] #探索保留

#DFS
for i in range(n):
    if seen[i] == 0:
        element = [] #連結要素
        seen[i] = 1
        todo.append(i)
        element.append(i)
        while todo != []:
            for j in friend[todo[-1]]:
                if seen[j] == 0:
                    seen[j] = 1
                    todo.append(j)
                    element.append(j)
                    break
            else:
                del todo[-1]
        length = len(element)
        for j in element:
            block[j] = [k for k in block[j] if k in element]
            size[j] = length - len(friend[j]) - len(block[j]) - 1
        
    print(size[i])

### FIXED CODE ###

# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # parents
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # find(x)
    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # union(x, y)
    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # same(x, y)
    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # size(x)
    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

import sys
def input():
    return sys.stdin.readline().strip()

n, m, k = map(int, input().split())
ans = [-1 for _ in range(n)]
uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    ans[a-1] -= 1
    ans[b-1] -= 1

for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1

for i in range(n):
    ans[i] += uf.size(i)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

l, r = map(int, input().split())
if l - r >= 2019:
    print(0)
else:
    mi = 10 ** 4
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            mi = min((i * j) % 2019, mi)
    print(mi)

### FIXED CODE ###

l, r = map(int, input().split())
if r - l >= 2019:
    print(0)
else:
    mi = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            mi = min((i * j) % 2019, mi)
    print(mi)
### BUGGY CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

ans=0
a=1
for i in range(k+1):
    ans+=a*m*pow(m-1,n-1-i,998244353)
    a=a*(n-1-i)//(i+1)
print(ans%998244353)

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m,k=n1()

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

ans=0
a=1
MOD=998244353
fac, ifac = make_tables(MOD, n-1)
        
for i in range(k+1):
    ans+=m*pow(m-1,n-1-i,998244353)*cmb(n-1, i, MOD, fac, ifac)
print(ans%998244353)