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

N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N):
  for j in range(i+1,N):
    m = 0
    x = i + dp[i-1][j-1] if i>1 else i
    y = j + dp[i-1][j-1] if i>1 else j
    while x<j and y<N and S[x]==S[y]:
      x += 1
      y += 1
      m += 1
#    print(pm,i,j)
    if m>ans:
      ans = m
    dp[i][j] = m
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
dp = [[0]*N for i in range(N)]
pm = 0
ans = 0
for i in range(N-1,0,-1):
  for j in range(i-1,-1,-1):
    if S[i]==S[j]:
      if i<N-1:
        dp[i][j] = min(dp[i+1][j+1]+1, i-j)
      else:
        dp[i][j] = 1
    else:
      dp[i][j] = 0
    if dp[i][j]>ans:
      ans = dp[i][j]
print(ans)
### BUGGY CODE ###

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

for j in range(n):
  if a[j]%2 == 0:
    arr = []
    temp = a[j]
    for i in range(2, int(-(-a[j]**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([a[j], 1])
        
    count = count + arr[0][1]
    
print(count)

### FIXED CODE ###

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

for i in range(n):
  count = 0
  temp = a[i]
  while (temp%2 == 0):
    temp = temp//2
    count = count + 1
    
  ans = ans + count
  
print(ans)
### BUGGY CODE ###

import sys

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

if(N%2 == 0):
    a.sort()
    for i in range(N//2):
        n = 2*i + 1
        if(a.count(n) != 2):
            print(0)
            sys.exit()
    print(2 ** (N//2))
else:
    a.sort()
    if(a.count(0) != 1):
        print(0)
        sys.exit()

    for i in range((N-1)//2):
        n = 2*(i+1)
        if(a.count(n) != 2):
            print(0)
            sys.exit()
    print(2 ** ((N-1)//2))


### FIXED CODE ###

import sys

MOD = 1000000007

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

if(N%2 == 0):
    a.sort()
    for i in range(N//2):
        n = 2*i + 1
        if(a[2*i] != n or a[2*i + 1] != n):
            print(0)
            sys.exit()
    print((2 ** (N//2)) % MOD)
else:
    a.sort()
    if(a.count(0) != 1):
        print(0)
        sys.exit()
    for i in range((N-1)//2):
        n = 2*i + 2
        if(a[2*i + 1] != n or a[2*i + 2] != n):
            print(0)
            sys.exit()
    print((2 ** ((N-1)//2)) % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

C = Factorial(2 * 10 ** 6 + 5, MOD).comb

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

ans = 0
for i in range(c2 - c1 + 1):
    tmp = C(r2 + c2 + 1 - i, r2) - C(r1 + c2 - i, r1 - 1)
    # print (tmp, C(r2 + c2 + 1 - i, r2), C(r1 + c2 - i, r1 - 1))

    ans += tmp
    ans %= MOD

print (ans)


### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())
MOD = 10 **9 + 7

ans = 0

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

F = Factorial(r2 + c2 + 3, MOD)

ans = F.comb(c1 + r1, c1) - F.comb(c1 + r2 + 1, c1) - F.comb(c2 + r1 + 1, c2 + 1) + F.comb(c2 + r2 + 2, c2 + 1)

print (ans % MOD)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9+7
import itertools
ans = 0
for a in itertools.combinations(A,K):
  ans += (max(a)-min(a))%mod
  ans %= mod
  
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
fact_l=[1]*(N+10)
mod = 10**9+7
for i in range(2,N+1):
  fact_l[i]=(fact_l[i-1]*i)%mod
  
fact_inv_l = [1]*(N+10)
for i in range(2,N+1):
  fact_inv_l[i]=pow(fact_l[i],mod-2,mod)
ans = 0
for i in range(1,N-K+2):
  b = N-i
  c = K-1
  ans -= A[i-1]*fact_l[b]%mod*fact_inv_l[b-c]%mod*fact_inv_l[c]%mod
  ans += A[-i]*fact_l[b]%mod*fact_inv_l[b-c]%mod*fact_inv_l[c]%mod
    
print(ans%mod)
### BUGGY CODE ###

def frac(n):
  sum = 1
  for i in range(1,n+1):
    sum*=i
  return sum

import sys,fractions
N,M=map(int,input().split(' '))
# abs(N-M) > 1なら無理
if (abs(N-M) > 1):
  print(0)
  sys.exit()

# それぞれの階乗を求める
frac_n = frac(N)
frac_m = frac(M)

if N == M:
  ans = frac_m * frac_n * 2
else:
  ans = frac_n * frac_m

print(ans % (10**9 + 7))

### FIXED CODE ###

divisor = 10**9 + 7

def frac(n):
  sum = 1
  for i in range(1,n+1):
    sum = sum * i % divisor
  return sum

import sys,fractions
N,M=map(int,input().split(' '))
# abs(N-M) > 1なら無理
if (abs(N-M) > 1):
  print(0)
  sys.exit()

# それぞれの階乗を求める
frac_n = frac(N)
frac_m = frac(M)

if N == M:
  ans = frac_m * frac_n * 2
else:
  ans = frac_n * frac_m

print(ans % (10**9 + 7))
### BUGGY CODE ###


def main():
  N, Q = [int(x) for x in input().split()]
  S = input()
  for i in range(Q):
    l, r = [int(x) for x in input().split()]
    sub = S[l - 1:r]
    print(sub.count('AC'))


if __name__ == "__main__":
  main()


### FIXED CODE ###

def main():
  N, Q = map(int, input().split())
  S = input()
  counts = [0] * (N + 1)
  for i in range(0, len(S)):
    counts[i + 1] = counts[i] + (1 if S[i:i + 2] == 'AC' else 0)
  for i in range(Q):
    l, r = map(int, input().split())
    print(counts[r - 1] - counts[l - 1])


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

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]
  field.sort()

  rng=[]
  for x,y in field:
    for z in range(x,y+1):
      rng.append(z)

  # print(rng)

  dp=[0]*(n+1)
  dp[1]=1

  rng_mx=len(rng)
  for i in range(1,n):
    for j,dx in enumerate(rng[:rng_mx]):
      if i+dx>n:
        rng_mx=j+1
        break
      dp[i+dx]+=dp[i]
      dp[i+dx]%=mod
    # print(dp)
  
  return dp[n]%mod

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]

  dp=[0]*(n+1)
  dpsum=[0]*(n+1)
  dp[1]=1
  dpsum[1]=1

  for i in range(2,n+1):
    for l,r in field:
      li=i-r
      ri=i-l
      if ri<=0:
        continue
      li=max(1,li)
      dp[i]+=dpsum[ri]-dpsum[li-1]
      dp[i]%=mod
    dpsum[i]=dp[i]+dpsum[i-1]
    dpsum[i]%=mod
  
  return dp[n]%mod

# main()
print(main())
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    print(0)
    s = S()
    if s == "Vacant":
        return
    x = s
    ok = 0
    ng = n
    while 1:
        mid = (ok + ng) // 2
        print(mid,flush=True)
        s = S()
        if s == "Vacant":
            return
        if mid & 1 == ok & 1:
            if s == x:
                ok = mid
            else:
                ng = mid
        else:
            if s == x:
                ng = mid
            else:
                ok = mid
                s = x

    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    print(0,flush = True)
    s = S()
    if s == "Vacant":
        return
    x = s
    ok = 0
    ng = n
    while 1:
        mid = (ok + ng) // 2
        print(mid, flush=True)
        s = S()
        if s == "Vacant":
            return
        if mid & 1 == ok & 1:
            if s == x:
                ok = mid
            else:
                ng = mid
        else:
            if s == x:
                ng = mid
            else:
                ok = mid
                x = s

    return


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

import math;

def swap(a,b):
    return (b,a)

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

def main():
    l,r = map(int,input().split())
    mod = 2019
    r = min(r,l+mod*2)
    ans = 2018
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            x = i * j % mod
            ans = min(ans,x)
    print(ans)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math;

def swap(a,b):
    return (b,a)

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

def main():
    l,r = map(int,input().split())
    mod = 2019
    r = min(r,l+mod*2)
    ans = 2018
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            x = i * j % mod
            ans = min(ans,x)
    print(ans)
    return

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

N = int(input())
x = int(N**0.5)
ans_1 = N

for i in range(N):
    if N % x == 0:
        ans_1 = x
        break
    else:
        x += 1

ans_2 = N//ans_1
print(ans_1 + ans_2 - 2)


### FIXED CODE ###

N = int(input())
x = int(N**0.5)+1
ans_1 = N

for i in range(x):
    if N % x == 0:
        ans_1 = x
        break
    else:
        x -= 1

ans_2 = N//ans_1
print(ans_1 + ans_2 - 2)
### BUGGY CODE ###

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

ans = [0] * n
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        ans[i] ^= a[j]

print(*ans)

### FIXED CODE ###

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

tmp = int(0)
for t in a:
    tmp ^= t

ans = [0] * n
for i in range(n):
    ans[i] = tmp ^ a[i]

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

# coding: utf-8
# Your code here!

def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

ans=0
for n in range(N):
    temp=A[:]
    temp.pop(n)
    for i in range(N-2):
        temp[i+1]=euclid(temp[i],temp[i+1])
    ans=max(temp[-1],ans)
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

org_A=A[:]
#左から最大公約数作る右もね
A=A[::-1]
l=[A.pop(-1)]
while A:
    l.append(euclid(l[-1],A.pop(-1)))

A=org_A
r=[A.pop(-1)]
while A:
    r.append(euclid(r[-1],A.pop(-1)))
r=r[::-1]

ans=0
#print(l,r)
for i in range(N):
    temp=euclid(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    #print(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    ans=max(ans,temp)

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

def solve(N, M, edges):
  inbound = {}
  for s,t in edges:
    if t in inbound:
      inbound[t].append(s)
    else:
      inbound[t] = [s]

  dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

  for s,t in edges:
    dp[s][t] = 1

  max_so_far = 0
  for i in range(1, N + 1):
    for s in range(1, N + 1):
      for t in range(1, N + 1):
        t_inbound = inbound[t] if t in inbound else []
        for t_i in t_inbound:
          # dp[s][t] = max(dp[s][t], dp[s][t_i] + 1)
          # max_so_far = max(max_so_far, dp[s][t])
          temp = dp[s][t_i] + 1
          if temp > dp[s][t]:
            dp[s][t] = temp
          if temp > max_so_far:
            max_so_far = temp

  print(max_so_far)


def iln(): return list(map(int, input().split()))


N, M = iln()
edges = []
for i in range(M):
  edges.append(iln())
  
solve(N, M, edges)

### FIXED CODE ###

from collections import defaultdict, deque

def solve(N, M, edges):
  outbound = defaultdict(deque)
  in_degree = defaultdict(int)
  for s,t in edges:
    outbound[s].append(t)
    in_degree[t] += 1

  q = deque()
  for i in range(N + 1):
    if in_degree[i] == 0:
      q.append(i)

  dp = [0 for _ in range(N + 1)]

  while q:
    node = q.popleft()
    for child in outbound[node]:
      dp[child] = max(dp[child], dp[node] + 1)
      in_degree[child] -= 1
      if in_degree[child] == 0:
        q.append(child)

  print(max(dp))


def iln(): return list(map(int, input().split()))


N, M = iln()
edges = []
for i in range(M):
  edges.append(iln())
  
solve(N, M, edges)
### BUGGY CODE ###

from math import floor
def main():
    a, b, n = map(int, input().split())

    r = 0
    for i in range(n+1):
        r = max(r, floor(a*i/b) - floor(i/b)*a)
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from math import floor
def main():
    a, b, n= map(int, input().split())
    x = min(n, b - 1)
    r = floor((a * x) / b) - a * floor(x / b)
    print(r)

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

def m():
    s = input()
    q = int(input())
    inv = 0
    pre = ''
    sub = ''

    for i in range(q):
        raw = input().split()
        if len(raw) == 1:
            inv = inv ^ 1
        else:
            f = int(raw[1])-1
            c = raw[2]
            if inv==f:
                pre = c + pre
            else:
                sub = sub + c
    
    if inv==0:
        print(pre+s+sub)
    else:
        print(sub[::-1]+s[::-1]+pre[::-1])

m()

### FIXED CODE ###

def m():
    s = input()
    q = int(input())
    inv = 0
    pre = []
    sub = []

    for i in range(q):
        raw = input().split()
        if len(raw) == 1:
            inv = inv ^ 1
        else:
            f = int(raw[1])-1
            c = raw[2]
            if inv==f:
                pre.append(c)
            else:
                sub.append(c)
    
    if inv==0:
        print(''.join(pre[::-1])+s+''.join(sub))
    else:
        print(''.join(sub[::-1])+s[::-1]+''.join(pre))

m()
### BUGGY CODE ###

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

balls = []
for k in range(n):
    ball=[a[i] for i in range(n) if i!=k]
    balls.append(ball)

ans = []
for k in range(n):
    cnt=0
    for i in range(len(balls)-1):
        for j in range(i+1,len(balls)-1):
            if balls[k][i]==balls[k][j]:
                cnt+=1
    print(cnt)


### FIXED CODE ###

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

count={}
for ak in a:
    if ak not in count:
        count[ak] = 0
    count[ak] += 1

sum=0
for key in count:
    sum += count[key]*(count[key]-1) // 2

for ak in a:
    print(sum-(count[ak]-1))
### BUGGY CODE ###



s = input()
q = int(input())

def addflont(s,c):
    text = "".join([c,s])
    return text
def addback(s,c):
    text = "".join([s,c])
    return text

reverse = 0

for i in range(q):
    t = input()
    if t[0]=="1":
        reverse = reverse^1
    if t[0]=="2":
        if t[2]=="1":
            if reverse==0:
                s = addflont(s,t[4])
            else:
                s = addback(s,t[4])
        elif t[2]=="2":
            if reverse==0:
                s = addback(s,t[4])
            else:
                s = addflont(s,t[4])

if reverse==1:
    print(s[::-1])
else:
    print(s)


### FIXED CODE ###



s = input()
q = int(input())

def addflont(s,c):
    text = "".join([c,s])
    return text
def addback(s,c):
    text = "".join([s,c])
    return text

reverse = 0
r = "";u = ""
for i in range(q):
    t = input()
    if t[0]=="1":
        reverse = reverse^1
    if t[0]=="2":
        if t[2]=="1":
            if reverse==0:
                r = addflont(r,t[4])
            else:
                u = addback(u,t[4])
        elif t[2]=="2":
            if reverse==0:
                u = addback(u,t[4])
            else:
                r = addflont(r,t[4])

s = r + s + u
if reverse==1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    P = []
    Y = []
    for _ in range(M):
        pi, yi = [int(i) for i in input().split()]
        P.append(pi)
        Y.append(yi)
    temp_list = []
    temp_dict = {}
    for i in range(N):
        for j in range(M):
            if P[j] == i+1:
                temp_list.append(Y[j])
        temp_list.sort()
        for i in range(len(temp_list)):
            temp_dict[str(temp_list[i])] = i+1
        temp_list = []

    for i in range(M):
        print(str(P[i]).zfill(6) + str(temp_dict[str(Y[i])]).zfill(6))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    Lw = []
    T = []
    for _ in range(M):
        pi, yi = [int(i) for i in input().split()]
        T.append(pi)
        T.append(yi)
        Lw.append(T)
        T = []
    temp_dict = {}
    answer_dict = {}
    L = Lw.copy()
    L.sort(key=lambda x: x[1])
    for i in range(N):
        temp_dict[str(i+1)] = 1
    for l in L:
        answer_dict[str(l[1])] = temp_dict[str(l[0])]
        temp_dict[str(l[0])] += 1

    for lw in Lw:
        print(str(lw[0]).zfill(6) + str(answer_dict[str(lw[1])]).zfill(6))


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

n=int(input())
A=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[True]*M
dep=[x for x in set(A) if A.count(x) >= 2]

for i in A:
    if cnt[i]==False:
        continue
    for j in range(2*i,M,i):
        #print(i,M,j)
        cnt[j]=False
ans=0
for i in set(A):
    if i in dep:
      continue
    if cnt[i]:
        ans+=1
print(ans)


### FIXED CODE ###

from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)
#print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque


if __name__ == '__main__':

    n, m = [int(s) for s in input().split(" ")]
    M = [[] for j in range(n)]
    for _ in range(m):
        u, v = [int(s) for s in input().split(" ")]
        M[u].append(v)
        M[v].append(u)
        
    color = [0] * n
    def dfs(u, c):  # depth-first search
        color[u] = c
        for v in range(n):
            if v in M[u] and color[v] == 0:
                dfs(v, c)
        color[u] = c
    
    c = 1
    for u in range(n):
        if color[u] == 0:
            dfs(u, c)
            c += 1
    
    l = int(input())
    for _ in range(l):
        p, q = [int(s) for s in input().split(" ")]
        if color[p] == color[q]:
            print("yes")
        else:
            print("no")



### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
import sys
sys.setrecursionlimit(200000)


if __name__ == '__main__':

    n, m = [int(s) for s in input().split(" ")]
    M = [set() for j in range(n)]
    for _ in range(m):
        u, v = [int(s) for s in input().split(" ")]
        M[u].add(v)
        M[v].add(u)
        
    color = [0] * n
    def dfs(u, c):  # depth-first search
        color[u] = c
        for v in M[u]:
            if color[v] == 0:
                dfs(v, c)
    
    c = 1
    for u in range(n):
        if color[u] == 0:
            dfs(u, c)
            c += 1
    
    l = int(input())
    for _ in range(l):
        p, q = [int(s) for s in input().split(" ")]
        if color[p] == color[q]:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    
    temp= many_int()
    temp = map(lambda x: 1<<(x-1), temp)
    sums = sum(temp)
    treasures.append(sums)

treasures

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index):
    for j in range(M):
        new_i = int(bin(treasures[j] | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()