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

import bisect
N = int(input())
A = sorted(int(input()) for _ in range(N))
B = sorted(int(input()) for _ in range(N))
mod = 10**9 + 7
ans = 1
b = bisect.bisect
for i in range(N):
    if A[i] < B[i]:
        ans *= 1 + i - b(B[:i], A[i])
    else:
        ans *= 1 + i - b(A[:i], B[i])
    ans %= mod
print(ans)


### FIXED CODE ###

N = int(input())
E = []
for _ in range(N):
    E += [(int(input()), 1)]
for _ in range(N):
    E += [(int(input()), -1)]
E.sort()
mod = 10**9 + 7
ans = 1
ab = 0
for e in E:
    if e[1] * ab < 0:
        ans *= abs(ab)
        ans %= mod
    ab += e[1]
print(ans)
### BUGGY CODE ###

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

while k:
    if a>=1:
        a-=1
    elif b>=1:
        b-=1
    k-=1

print(a,b)

### FIXED CODE ###

def solve(a,b,k):
    if a==0 and b==0:
        return '0 0'
    if a>=k:
        str = '%d %d' % (a-k,b)
        return str
    else:
        b = b + a - k
        a = 0
        if b<0:
            return '0 0'
        str = '0 %d' % (b)
        return str 
        

a,b,k = map(int, input().split())
print(solve(a,b,k))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

ans=0
N,M=map(int,input().split())
Ar=[]
for _ in range(M):
     Ar.append([])
for _ in range(N):
      A,B=map(int,input().split())
      if A <= M:
          Ar[A-1].append(B)
An=[]
for i in range(M):
      An += Ar[i]
      if len(An)>0:
          An.sort()
          ans+=An.pop(len(An)-1) 
print(ans)


### FIXED CODE ###

import heapq
N , M = map(int , input().split())
jobs = [list(map(int , input().split())) for _ in range(N)]
jobs.sort()

q = []
index = 0
ans = 0
for limit in range(1 , M + 1):
    while index < N:
        time =jobs[index][0]
        reward = jobs[index][1]
        if limit >= time:
            heapq.heappush(q , -reward)
            index += 1
        else:
            break
    #print(q)
    if len(q) != 0:
        tmp = heapq.heappop(q)
        ans -= tmp

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

import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.zeros((n+1, w+1))

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))
### BUGGY CODE ###

import sys
import os
import fractions

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    K=int(input())
    # map(int, input().split())
    sum=0

    for a in range(1,K+1):
        for b in range(1,K+1):
            tmp=fractions.gcd(a,b)
            for c in range(1,K+1):
                sum+=fractions.gcd(tmp,c)

    print(sum)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import itertools

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def gcd(a,b):
    if b==0: return a
    else: return gcd(b,a%b)

def main():
    #file_input()
    K=int(input())
    # map(int, input().split())
    sum=0

    combi_l = itertools.combinations_with_replacement(range(1,K+1),3)
    # print(combi_l)

    for combi in combi_l:
        # print(combi)
        if combi[0]==combi[1]==combi[2]:
            sum+=gcd(gcd(combi[0],combi[1]),combi[2])
        elif combi[0]==combi[1] or combi[1]==combi[2] or combi[2]==combi[0]:
            sum+=3*gcd(gcd(combi[0],combi[1]),combi[2])
        else:
            sum+=6*gcd(gcd(combi[0],combi[1]),combi[2])

    # for a in range(1,K+1):
    #     for b in range(1,K+1):
    #         tmp=fractions.gcd(a,b)
    #         for c in range(1,K+1):
    #             sum+=fractions.gcd(tmp,c)

    print(sum)

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

def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    X = sorted([list(map(int,input().split())) for i in range(n)])
    mod = 998244353
    e = [[] for i in range(n)]

    def dfs(x):
        count = 1

        for i in e[x]:
            count *= dfs(i)
            count %= mod
        return count+1

    q = deque([])

    for i in range(n-1,-1,-1):
        a,b = X[i]
        while q and q[0][0] < a+b:
            e[i].append(q[0][1]) 
            q.popleft()
        q.appendleft([a,i])

    ans = 1
    for i,j in q:
        ans *= dfs(j)
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    X = sorted([list(map(int,input().split())) for i in range(n)])
    mod = 998244353
    e = [[] for i in range(n)]

    def dfs(x):
        count = 1

        for i in e[x]:
            count *= dfs(i)
            count %= mod
        return count+1

    q = deque([])

    for i in range(n-1,-1,-1):
        a,b = X[i]
        while q and q[0][0] < a+b:
            e[i].append(q[0][1]) 
            q.popleft()
        q.appendleft([a,i])

    ans = 1
    for i,j in q:
        ans *= dfs(j)
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
N = len(S)
for _ in range(N//2):
    S = S.replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','').replace('01','').replace('10','')

    if S.count('01') == 0 and S.count('10') == 0:
        break
print(N - len(S))

### FIXED CODE ###

S = input()
r = S.count('0')
b = S.count('1')
print(min(r,b)*2)
### BUGGY CODE ###

def main():
    n = int(input())
    a_s = [int(input()) for _ in range(n)]
    for i in range(n):
        print(max(a_s[:i] + a_s[i+1:]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a_s = [int(input()) for _ in range(n)]
    maximum = max(a_s)
    idx_max = a_s.index(maximum)
    second = max(a_s[:idx_max] + a_s[idx_max+1:])
    for i in range(n):
        if i == idx_max:
            print(second)
        else:
            print(maximum)


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

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

if n <= 2:
    print(0)
else:
    cnt = 0

    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                l = sorted([li[i], li[j], li[k]])

                if l[0] + l[1] > l[2]:
                    cnt += 1

    print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)

cnt = 0

for i in range(n):
    for j in range(i+1, n):
        x = bisect.bisect_left(l, l[i]+l[j])
        cnt += x-j-1

print(cnt)
### BUGGY CODE ###

(R,C,K),*rcv = [list(map(int, s.split())) for s in open(0)]

grids = [[0]*C for _ in range(R)]

for r,c,v in rcv:
    grids[r-1][c-1] = v

from collections import defaultdict
dp = defaultdict(int)

for r in range(R):
    for c in range(C):
        value = grids[r][c]
        for i in range(1,4):
            dp[r,c,i] = dp[r,c-1,i]
            if i == 1:
                dp[r,c,i] = max(dp[r,c,i], max(dp[r-1,c,j] for j in range(1,4)) + value)
            dp[r,c,i] = max(dp[r,c,i], dp[r,c-1,i-1] + value)

print(max(dp[R-1,C-1,j] for j in range(4)))

### FIXED CODE ###

# from sys import stdin
# input = stdin.readline
(R,C,K) = map(int, input().split())
rcv = [list(map(int, input().split())) for _ in range(K)]
 
grids = [[0]*C for _ in range(R)]
 
for r,c,v in rcv:
    grids[r-1][c-1] = v
 
dp = [0] * C

for r in range(R):
#     print(dp)
    ndp = [0] * C
    elm = [0] * 4
    for c in range(C):
        elm[0] = max(elm[0], dp[c])
        value = grids[r][c]
        if value:
            nelm = [0] * 4
            nelm[0] = elm[0]
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            for i in range(3)[::-1]:
                nelm[i + 1] = max(elm[i + 1], elm[i] + value)
#             print(f'{value=}')
#             print(f'{ elm=}')
#             print(f'{nelm=}')
            elm = nelm
        ndp[c] = max(elm)
    dp = ndp
 

print(dp[-1])
### BUGGY CODE ###

def main():
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = [0]*(n-m)

    for use in range(m, 1, -1):
        rest = ans
        nex = now_a[0]
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            for i in range(start-1, max(-1, start-1-rest), -1):
                if now_a[i] == max_a[i]:
                    if start != m:
                        nex = now_a[start]
                    break
                elif now_a[i] == 0:
                    cnt += 1
                now_a[i] += 1
                rest -= 1
        while cnt >= use:
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                flag = 0
                if now_a[start] == 1:
                    flag = 1
                end = min(end, bl(now_a, val+1), start+rest)
                for i in range(start, end):
                    cnt -= flag
                    now_a[i] -= 1
                    rest -= 1
                end = start
        ans_list.append(ans)
    print(n)
    for i in ans_list[::-1]:
        print(i)


main()


### FIXED CODE ###

def main():
    from collections import Counter as ct
    from bisect import bisect_left as bl

    n = int(input())
    max_a = sorted(ct(list(map(int, input().split()))).values())
    now_a = [i for i in max_a]
    m = len(max_a)
    cnt = m
    ans = 0
    ans_list = []

    for use in range(n, 0, -1):
        rest = ans
        nex = now_a[0]
        # restの分だけ戻す
        while rest:
            val = nex
            start = bl(now_a, val+1)
            nex += 1
            for i in range(start-1, -1, -1):
                if now_a[i] == max_a[i]:
                    if start != m:
                        nex = now_a[start]
                    break
                elif now_a[i] == 0:
                    cnt += 1
                now_a[i] += 1
                rest -= 1
                if rest == 0:
                    break
        # 大きい方から使っていく
        while True:
            if cnt < use:
                ans_list.append(ans)
                break
            ans += 1
            rest = use
            nex = now_a[-1]
            end = m
            while rest:
                val = nex
                start = bl(now_a, val)
                if start != 0:
                    nex = now_a[start-1]
                for i in range(start, end):
                    if now_a[i] > val:
                        break
                    elif now_a[i] == 1:
                        cnt -= 1
                    now_a[i] -= 1
                    rest -= 1
                    if rest == 0:
                        break
                end = start
    for i in ans_list[::-1]:
        print(i)


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
      	if next == prev:
        	continue
      	else:
          dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
 
def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
      	if next == prev:
        	continue
      	else:
          dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

#初期のカウンター
ans=[0]*n

#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))
### BUGGY CODE ###

N = int(input()) + 1
A = [0] + [int(i) for i in input().split()]

MAX_I = 10 ** 9
cnt = 0

for i in range(1, N):
    if MAX_I >= i + A[i]:
        for j in range(i + A[i], N):
            if (j - i) == (A[i] + A[j]):
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
i_Ai = {}
cnt = 0

for i, h in enumerate(A):
	imh = i - h
	if imh in i_Ai:
		cnt += i_Ai[imh]
	iph = i + h
	if iph in i_Ai:
		i_Ai[iph] += 1
	else:
		i_Ai[iph] = 1
print(cnt)
### BUGGY CODE ###

l,r = map(int, input().split())
L = l % 2019
R = r % 2019
ans = []

if R - L > 0:
  for i in range(l, r+1):
    for j in range(i+1, r+1):
      ans.append(i * j % 2019)
  print(min(ans))
else:
  print(0)

### FIXED CODE ###

l,r = map(int, input().split())
L = l % 2019
R = r % 2019
ans = []

if r - l > 2019:
  print(0)
elif R - L > 0:
  for i in range(L, R):
    for j in range(i+1, R+1):
      ans.append(i * j % 2019)
  print(min(ans))
else:
  print(0)
### BUGGY CODE ###


N = int(input())
A = list(map(int, input().split()))[::-1]

ans = []

for i in range(N):
  j = N - i
  cnt = 0 

  for m in [n for n in range(j, N+1) if (n % j == 0) and (n != j) ]:
    cnt += A[N - m]
  
  if (cnt + A[i]) % 2 == 1:
    ans.append(j)

len_ans = len(ans)
if len_ans == 0:
  print(0)
else:
  print(len_ans)
  print(*ans[::-1])

### FIXED CODE ###


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

for i in list(range(1, N+1))[::-1]:
  tmp = i
  cnt = 0
  while tmp <= N:
    if tmp in B:
      cnt += 1    
    tmp += i

  if cnt % 2 != A[i-1]:
    B.add(i)

len_b = len(B)
if len_b == 0:
  print(0)
else:
  print(len_b)
  print(*sorted(list(B)))
### BUGGY CODE ###

import numpy as np

N = int(input())
X = np.zeros([N,2], dtype=int)

for i in range(N):
    X[i] = list(map(int, input().split()))  
left = X[:,0] - X[:,1]
right = X[:,0] + X[:,1]
lr = np.concatenate([left.reshape(-1,1), right.reshape(-1,1)], 1)

r_min = np.argmin(right)
use = lr[r_min].reshape(-1,2)
while use[-1,1] <= np.max(left):
    lr = lr[np.all(lr >= use[-1,1], axis=1),:]
    r_min = np.argmin(lr[:,1])
    use = np.vstack([use, lr[r_min]])
print(len(use))

### FIXED CODE ###

import numpy as np

N = int(input())
X = np.zeros([N,4], dtype=int)

for i in range(N):
    X[i,0], X[i,1] = map(int, input().split())
    X[i,2], X[i,3] = X[i,0] - X[i,1], X[i,0] + X[i,1]    

col_num = 3
X = X[np.argsort(X[:, col_num])]
cnt = 1
r_min = X[0,3]
for i in range(1,N):
    if X[i,2] >= r_min:
        cnt += 1
        r_min = X[i,3]
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    n= int(input())
    s = str(input())
    ans = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range (j+1,n):
                t = {s[i], s[j], s[k]}
                if j-i != k-j and len(t) ==3:
                    ans +=1
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    n= int(input())
    s = str(input().rstrip())
    r= s.count('R')
    g=s.count('G')
    b = s.count('B')
    ans = 0
    for i in range(n-2):
        for j in range(i+1, (n+i+1)//2):
            k = 2*j-i
            t = {s[i], s[j], s[k]}
            if len(t) ==3:
                ans +=1
    print(r*g*b-ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

ID = [1]*N #IDカードの配列を用意する
for i in range(M):
    for j in range(N):
        if LR[i][0]-1<=j and j<=LR[i][1]-1: #通過できる場合は1をかける
            ID[j] = ID[j]*1
        else: #通過できない場合は0をかける
            ID[j] = ID[j]*0
print(sum(ID)) #全てのゲートをチェックした後、1のままのカードは全てのゲートを通過可能


### FIXED CODE ###

N, M = map(int,input().split())
list_L = []
list_R = []
for i in range(M):
    L, R = map(int,input().split())
    list_L.append(L)
    list_R.append(R)
print(min(list_R)-max(list_L)+1 if min(list_R)>=max(list_L) else 0)
### BUGGY CODE ###

s = str(input())
n = len(s)
for i in range(n):
  if s[i] == "?":
    if i == 0:
      s = "D" + s[i+1:]
    else:
      s = s[:i] + "D" + s[i+1:]
print(s)

### FIXED CODE ###

s = str(input())
n = len(s)
t= list(s)
ans = ""
for i in range(n):
  if t[i] == "?":
    t[i] = "D"

ans = ''.join(t)

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

a,b,n=map(int,input().split())
score=0
for i in range(1,n+1):
    t = int(a*i/b)-a*int(i/b)
    score = max(score,t)
print(score)

### FIXED CODE ###

a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
elif(b==1):
    print(0)
else:
    c = int(n/b)
    score = 0
    for i in range(1,c+1):
        n_ = b*i-1
        t = int(a*n_/b)-a*int(n_/b)
        score = max(score,t)
    t = int(a*n/b)-a*int(n/b)
    score = max(score,t)
    print(score)
### BUGGY CODE ###

from functools import reduce

if __name__ == "__main__":
    N = int(input())
    A = input().split()
    ans = 1
    for i in range(N):
        ans *= int(A[i])

    if ans > 10**18:
        ans = -1
    print(ans)
         


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    A = sorted(list(map(int, input().split())))
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

import math

s = input()
li = [0 for _ in range(len(s))]

for i in range(len(s)):
    if s[i] == "R":
        c = 1
        while True:
            ni = i + c
            if s[ni] == "L":
                if c % 2 != 0:
                    li[ni - 1] += 1
                else:
                    li[ni] += 1
                break
            c += 1
    else:
        c = 1
        while True:
            ni = i - c
            if s[ni] == "R":
                if c % 2 != 0:
                    li[ni + 1] += 1
                else:
                    li[ni] += 1
                break
            c += 1

print(" ".join(map(str, li)))

### FIXED CODE ###

import math

s = input()
li = [0 for _ in range(len(s))]

for i in range(len(s)):
    if s[i] == "R":
        t = s[i:].index("L")
        if t % 2 != 0:
            li[i + t - 1] += 1
        else:
            li[i + t] += 1
    else:
        t = s[:i].rfind("R")
        if (i - t) % 2 != 0:
            li[t + 1] += 1
        else:
            li[t] += 1

print(*li)
### BUGGY CODE ###

from math import ceil

N,A,B=map(int,input().split())
h=[int(input()) for _ in range(N)]

def f(k):
    g=lambda x:ceil((x-B*k)/(A-B))
    return(sum(filter(lambda x:x>0,map(g,h)))<=k)

l,r=0,ceil(max(h)/B)

while r-l>1:
    if f((l+r)//2):
        r=(l+r)//2
    else:
        l=(l+r)//2

print(r)

### FIXED CODE ###

n,a,b=map(int,input().split())
h=[int(input()) for _ in [0]*n]
f=lambda n:lambda x:x-b*n

def calc(n):
  g=f(n)
  k=lambda x:1+x//(a-b) if x%(a-b) else x//(a-b)
  o=filter(lambda x:x>0,map(g,h))
  *p,=map(k,o)
  if not p:
    return True
  else:
    return sum(p)<=n

l,r=0,max(h)
while r-l>1:
  m=(r+l)//2
  if calc(m):
    r=m
  else:
    l=m
print(r)
### 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(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = set([int(input()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
print(dp[N])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m,k = map(int,input().split())
f = []
h = []
t = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  f.append((a,b))
  t[a].append(b)
  t[b].append(a)
for _ in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  h.append((a,b))
ans = [0]*n
c = [False]*n

def dfs(d):
  c[d] = True
  ret=[]
  for i in t[d]:
    if not c[i]:
      ret += dfs(i)
  return [d] + ret
m = []
for i in range(n):
  if not c[i]:
    e = dfs(i)
    m.append(set(e))
    g = len(e)-1
    for j in e:
      ans[j] = g
for i,j in f:
  ans[i]-=1
  ans[j]-=1
for i,j in h:
  for k in m:
    o = len(k & set((i,j)))
    if o == 2:
      ans[i]-=1
      ans[j]-=1
      break
    elif o == 1:
      break
print(*ans)

### FIXED CODE ###

n,m,k = map(int,input().split())
root = [i for i in range(n)]
height = [1 for i in range(n)]
def find(n):
  sn = n
  while n != root[n]:
    n = root[n]
  root[sn] = n
  return n
def union(a,b):
  a = find(a)
  b = find(b)
  if a==b:
    return
  elif height[a]>=height[b]:
    height[a] += height[b]
    height[b] = 0
    root[b] = a
  else:
    height[b] += height[a]
    height[a] = 0
    root[a] = b
l = [set() for _ in range(n)]
for i in range(m):
  a,b = map(lambda x:int(x)-1,input().split())
  union(a,b)
  l[a].add(b)
  l[b].add(a)
for i in range(k):
  a,b = map(lambda x:int(x)-1,input().split())
  if find(a)==find(b):
    l[a].add(b)
    l[b].add(a)
print(*[height[find(i)]-len(l[i])-1 for i in range(n)])
### BUGGY CODE ###

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

dp = [[10**10 for _ in range(2**n)] for j in range(m)]
dp[0][0] = 0
a, b = map(int, input().split())
c = list(map(int, input().split()))
idx = 0
for cc in c:
  idx += 2**(cc-1)
for j in range(1, 2**n):
  if ~idx & j == 0:
    dp[0][j] = a

for i in range(1, m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  idx = 0
  for cc in c:
    idx += 2**(cc-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j], dp[i-1][(j|idx)^idx]+a)

if dp[-1][-1] != 10**10:
  print(dp[-1][-1])
else:
  print(-1)

### FIXED CODE ###

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

dp = [[10**10 for _ in range(2**n)] for j in range(m)]
dp[0][0] = 0
a, b = map(int, input().split())
c = list(map(int, input().split()))
idx = 0
for cc in c:
  idx += 2**(cc-1)
for j in range(1, 2**n):
  if ~idx & j == 0:
    dp[0][j] = a

for i in range(1, m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  idx = 0
  for cc in c:
    idx += 2**(cc-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j], dp[i-1][(j|idx)^idx]+a)

if dp[-1][-1] != 10**10:
  print(dp[-1][-1])
else:
  print(-1)