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

from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = np.array(floyd_warshall(graph),dtype="int32")

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

print(ans)

### FIXED CODE ###

##from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
##import numpy as np
from itertools import permutations
N,M,R = map(int,input().split())
r = list(map(int,input().split()))

"""
https://juppy.hatenablog.com/entry/2018/11/01/%E8%9F%BB%E6%9C%AC_python_%E5%85%A8%E7%82%B9%E5%AF%BE%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E6%B3%95%EF%BC%88%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
"""

def warshall_floyd(d):
    n = len(d)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

graph = [[float("inf") for i in range(N)] for j in range(N)] 
for i in range(M):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = C
    graph[B-1][A-1] = C

dist = warshall_floyd(graph)

ans = 1e10
for i in permutations(r):
    flag = True
    way = list(i)
    tmp = 0
    for i in range(len(way)-1):
        if dist[way[i]-1][way[i+1]-1] < 0:
            flag = False
            break
        tmp += dist[way[i]-1][way[i+1]-1]
    if flag:
        ans = min(tmp,ans)

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

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

MOD = 10**9+7
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
    dp[1] = 0

for i in range(1, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2])

print(dp[n] % MOD)


### FIXED CODE ###

MOD = 10**9+7
n, m = map(int, input().split())
A = [int(input()) for _ in range(m)]

safe = [True] * (n+1)
for a in A:
    safe[a] = False

dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1):
    if safe[i]:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD

print(dp[n])
### BUGGY CODE ###

L, R = map(int, input().split())
l = []
frag = False
if R - L >= 2019:
    l.append(0)
    frag = True
for i in range(L, R):
    for j in range(i+1, R+1):
        l.append((i*j) % 2019)
        n = len(l)
        if n % 2 == 0:
            if l[:n//2] == l[n//2:]:
                frag = True
                break
    if frag: break

print(min(l))

### FIXED CODE ###

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

from queue import Queue
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = Queue(3*N+1)
q.put((S, 0))
while not q.empty():
    v, l = q.get()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.put((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
INF = -1
dist = [[INF]*3 for _ in range(N)]
vector = [[] for _ in range(N)]

for i in range(M):
    graf1, graf2 = map(int, input().split())
    vector[graf1-1].append(graf2-1)
S, T = map(int, input().split())
S, T = S-1, T-1

# BFS
dist[S][0] = 0
q = deque()
q.append((S, 0))
while q:
    v, l = q.popleft()
    for i in vector[v]:
        new_l = (l+1)%3
        if dist[i][new_l] != INF:
            continue
        dist[i][new_l] = dist[v][l] + 1
        q.append((i, new_l))

ans = dist[T][0]
if ans == INF:
    print("-1")
else:
    print(int(ans/3))
### BUGGY CODE ###

from collections import deque

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

explored = [[False for i in range(W)] for j in range(H)]
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
ans = 0

for h in range(H) :
    for w in range(W) :
        if not explored[h][w] :
            q = deque([(h,w)])
            black = 0
            white = 0
            
            while q :
                y,x = q.popleft()
                explored[y][x] = True
                
                if MAP[y][x] == "#" :
                    black += 1
                else :
                    white += 1
                
                for dy,dx in dxy :
                    ny = y+dy
                    nx = x+dx
                    
                    if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
                        continue
                    if explored[ny][nx] :
                        continue
                    if MAP[ny][nx] == MAP[y][x] :
                        continue
                    if (ny,nx) in q :
                        continue
                    q.append((ny,nx))
                    
            ans += black*white

print(ans)


### FIXED CODE ###

from collections import deque

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

explored = [[False for i in range(W)] for j in range(H)]
dxy = [(-1,0),(1,0),(0,-1),(0,1)]
ans = 0

for h in range(H) :
    for w in range(W) :
        if not explored[h][w] :
            q = deque([(h,w)])
            black = 0
            white = 0
            
            while q :
                y,x = q.popleft()
                explored[y][x] = True
                
                if MAP[y][x] == "#" :
                    black += 1
                else :
                    white += 1
                
                for dy,dx in dxy :
                    ny = y+dy
                    nx = x+dx
                    
                    if (ny < 0) or (ny >= H) or (nx < 0) or (nx >= W) :
                        continue
                    if explored[ny][nx] :
                        continue
                    if MAP[ny][nx] == MAP[y][x] :
                        continue
                    if (ny,nx) in q :
                        continue
                    q.append((ny,nx))
                    
            ans += black*white

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

def main():
	n,p = map(int,input().split())
	s = [int(c) for c in input()][::-1]
	num = 0
	ans = 0
	if p == 2 or p == 5:
		for i in range(n):
			if s[i]%p == 0:
				ans += n-i
		print(ans)
		return
	arr = [0]*p
	arr[0]=1
	z = 1
	t = 0
	for ss in s:
		t = (t + z*ss)%p	
		z *=10 %p
		arr[t] += 1
	for l in arr:
		ans += l * (l - 1) // 2
	print(ans)
if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

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

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

ans = []
for i in range(1, n+1):
  ans.append(l.index(i)+1)

print(' '.join(map(str, ans)))

### FIXED CODE ###

import numpy as np

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

k = np.argsort(l)

for i in range(n):
  k[i]+=1

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

from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    qq = deque()
    ans += 1
    while que:
      nh, nw = que.popleft()
      if nw+1<=W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if  0<=nw-1 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh+1<=H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if 0<=nh-1 and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

s=input()
k=int(input())
uselist=[]
count=0
checker=0

alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
anslist=sorted(set(anslist))
print(anslist[k-1])
    
    

### FIXED CODE ###

s=input()
k=int(input())
uselist=[]
count=0
checker=0
alphabet="abcdefghijklmnopqrstuvwxyz"
while count<=5 and checker<=26:
    for i in alphabet:
        for j in range(len(s)):
            if s[j]==i:
                uselist.append((j,i))
                count+=1
        checker+=1
anslist=[]
for some in uselist:
    count=0
    for j in range(some[0],len(s)):
        anslist.append(s[some[0]:j+1:])
        count+=1
        if count>5:
            break
            
anslist=sorted(set(anslist))

print(anslist[k-1])
### BUGGY CODE ###

s = input()
t = input()

atoz = [chr(i) for i in range(97,97+26)]
s_list = [[] for i in range(26)]

for i in range(len(s)):
    for j in range(26):
        if s[i] == atoz[j]:
            s_list[j].append(1)
        else:
            s_list[j].append(0)

t_list = [[] for i in range(26)]

for i in range(len(t)):
    for j in range(26):
        if t[i] == atoz[j]:
            t_list[j].append(1)
        else:
            t_list[j].append(0)

s_sort = sorted(s_list)
t_sort = sorted(t_list)

if s_sort == t_sort:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys

s = input()
t = input()

# atoz = [chr(i) for i in range(97,97+26)]


for i in range(len(s)):
    if s[i] == t[i]:
        continue
    else:
        s_tmp = s
        s = s.translate(s.maketrans({s[i]:t[i], t[i]:s[i]}))
        if s_tmp[:i] != s[:i]:
            print("No")
            sys.exit()
        else:
            pass


if s == t:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys,math
n=int(input())
a=list(map(int,input().split()))
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
pointer=2
while pointer<10**6+1:
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    pointer2+=pointer
  if count>=2:
    flag=1
    break
  pointer+=1
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import sys,math
n=int(input())
a=list(map(int,input().split()))
sieve=[0]*(10**6+1)
numbers={}
flag=0
for i in range(n):
  if a[i] in numbers:
    numbers[a[i]]+=1
  else:
    numbers[a[i]]=1
pointer=2
while pointer<10**6+1:
  if sieve[pointer]==1:
    pointer+=1
    continue
  count=0
  pointer2=pointer
  while pointer2<10**6+1:
    if pointer2 in numbers:
      count+=numbers[pointer2]
    sieve[pointer2]=1
    pointer2+=pointer
  if count>=2:
    flag=1
    break
if flag==0:
  print('pairwise coprime')
  sys.exit()
ans=a[0]
for i in range(1,n):
  ans=math.gcd(a[i],ans)
if ans==1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

import collections as cl
N=int(input())
s_=[sorted(input()) for i in range(N)]

ans=0
result_=[]
for j in range(N):
    cnt=cl.Counter(s_[j]).items()
    for l in range(j):
        if cnt==result_[l]:
            ans+=1
        else:
            ans+=0

    result_.append(cnt)
print(ans)

### FIXED CODE ###

import collections as cl
import math
N=int(input())

result_=[]
for i in range(N):
    s= ''.join(sorted(input()))
    result_.append(s)

result=list(cl.Counter(result_).values())

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans=0
for j in range(len(result)):
    if result[j]==1:
        continue
    else:
        ans+=combinations_count(result[j],2)

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

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

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[float("inf")] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==float("inf")):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)

### FIXED CODE ###

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

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[2000] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==2000):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)
### BUGGY CODE ###

from heapq import heappush,heappop
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=[]
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.append(mod-t)
ans=ans[::-1]
for a in ans:
    print(a)

### FIXED CODE ###

from heapq import heappush,heappop
from collections import deque
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=deque()
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.appendleft(mod-t)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

N = int(input())
S = str(input())

cnt = []
count = 0

for i in range(len(S)):
    count = 0
    for j in range(len(S)):
        if i > j and S[j] == "W":
            count += 1
        if i < j and S[j] == "E":
            count += 1
    cnt.append(count)
print(min(cnt))

### FIXED CODE ###

N = int(input())
S = str(input())
cnt = []
count = 0

for i in range(1,len(S)):
    if S[i] == "E":
        count += 1
cnt = [count]*N

for i in range(1, len(S)):
    cnt[i] = cnt[i-1]
    if S[i-1] == "W":
        cnt[i] += 1
    if S[i] == "E":
        cnt[i] -= 1
print(min(cnt))
### BUGGY CODE ###

n,m = map(int,input().split())
brokensteps = [int(input()) for x in range(m)]
dp = [0] * (n+1)
for i in range(n+1):
    if i in brokensteps:
        dp[i] = 0
        continue
    
    elif i <= 1:
        dp[i] = 1

    else:
        dp[i] = (dp[i-1]%(10**9+7) + dp[i-2]%(10**9+7))%(10**9+7)

print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
brokensteps = set([int(input()) for x in range(m)])
dp = [0] * (n+1)
for i in range(n+1):
    if i in brokensteps:
        dp[i] = 0
        continue
    
    elif i <= 1:
        dp[i] = 1

    else:
        dp[i] = (dp[i-1] + dp[i-2])%(10**9+7)

print(dp[n])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().rstrip().split())
checked = [[-1]*W for i in range(H)]
black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(H):
    row = input().rstrip()
    for j in range(W):
        if row[j] == "#":
            checked[i][j] = 0
            black_list.append((i, j))


directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 黒の周辺4方向のうち、白だったら黒にする
while black_list:
    queue = deque(black_list)
    black_list = []
    while queue:
        x, y = queue.popleft()

        # 周囲探索
        for dx, dy in directions:
            xx = x + dx
            yy = y + dy

            if xx >= 0 and xx < H and yy >= 0 and yy < W:
                if checked[xx][yy] == -1:
                    checked[xx][yy] = checked[x][y] + 1
                    black_list.append((xx, yy))

        # # 上
        # if x-1 > -1 and checked[x-1][y] == -1:
        #     checked[x-1][y] = checked[x][y] + 1
        #     black_list.append((x-1, y))
        # # 下
        # if x+1 < H and checked[x+1][y] == -1:
        #     checked[x+1][y] = checked[x][y] + 1
        #     black_list.append((x+1, y))
        # # 左
        # if y-1 > -1 and checked[x][y-1] == -1:
        #     checked[x][y-1] = checked[x][y-1] + 1
        #     black_list.append((x, y-1))

        # # 右
        # if y+1 < W and checked[x][y+1] == -1:
        #     checked[x][y+1] = checked[x][y+1] + 1
        #     black_list.append((x, y+1))


ans = 0
for i in range(H):
    for j in range(W):
        if ans < checked[i][j]:
            ans = checked[i][j]
print(ans)


### FIXED CODE ###

H, W = map(int, input().rstrip().split())
checked = [[True]*(W+2)]
checked += [[True] + [ch == "#" for ch in input().rstrip()] + [True]
            for i in range(H)]
checked.append([True]*(W+2))

black_list = []
# 初期化
# 0 => 黒、 -1 => 白
for i in range(1, H+1):
    for j in range(1, W+1):
        if checked[i][j]:
            black_list.append((i, j))

# 黒の周辺4方向のうち、白だったら黒にする
ans = -1
while black_list:
    ans += 1
    tmp = []
    for x, y in black_list:
        # 上
        if not checked[x-1][y]:
            checked[x-1][y] = True
            tmp.append((x-1, y))
        # 下
        if not checked[x+1][y]:
            checked[x+1][y] = True
            tmp.append((x+1, y))
        # 左
        if not checked[x][y-1]:
            checked[x][y-1] = True
            tmp.append((x, y-1))

        # 右
        if not checked[x][y+1]:
            checked[x][y+1] = True
            tmp.append((x, y+1))

    black_list = tmp

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

n=int(input())
s=input()
a=[[0]*n for i in range(n)]
buf=0
for i in range(n):
    for j in range(i+1,n):
        if i==0:
            if s[i]==s[j]:
                a[i][j]=1
            continue
        if s[i]==s[j]:
            a[i][j]=min(j-i,a[i-1][j-1]+1)
            buf=max(buf,a[i][j])
print(buf)

### FIXED CODE ###

n=int(input())
s=input()
a=[[0]*n for i in range(n)]
buf=0
for i in range(n):
    for j in range(i+1,n):
        if i==0:
            if s[i]==s[j]:
                a[i][j]=1
            continue
        if s[i]==s[j]:
            a[i][j]=min(j-i,a[i-1][j-1]+1)
            buf=max(buf,a[i][j])
print(buf)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)


### FIXED CODE ###

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)