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

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

L = [[None for _ in range(W)] for _ in range(H)]
R = [[None for _ in range(W)] for _ in range(H)]
U = [[None for _ in range(W)] for _ in range(H)]
D = [[None for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1

for i in range(H):
    for j in reversed(range(W)):
        if s[i][j] == "#":
            R[i][j] = 0
        elif j == W-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1

for i in range(H):
    for j in range(W):
        if s[i][j] == "#":
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1

for i in reversed(range(H)):
    for j in range(W):
        if s[i][j] == "#":
            D[i][j] = 0
        elif i == H-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(H):
    for j in range(W):
        tmp = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        if tmp > ans:
            ans = tmp

print(ans)


### FIXED CODE ###

import numpy as np

H,W = map(int, input().split())
s = [list(input()) for j in range(H)]
s = (np.array(s) == ".") * 1

L = np.zeros((H, W), dtype = int)
R = np.zeros((H, W), dtype = int)
U = np.zeros((H, W), dtype = int)
D = np.zeros((H, W), dtype = int)


for j in range(W):
    if j == 0:
        L[:,j] = s[:,j]
    else:
        L[:,j] = (L[:,j-1] + 1) * s[:,j]
        

for j in reversed(range(W)):
    if j == W-1:
        R[:,j] = s[:,j]
    else:
        R[:,j] = (R[:,j+1] + 1) * s[:,j]


for i in range(H):
    if i == 0:
        U[i,:] = s[i,:]
    else:
        U[i,:] = (U[i-1,:] + 1) * s[i,:]

for i in reversed(range(H)):
    if i == H-1:
        D[i,:] = s[i,:]
    else:
        D[i,:] = (D[i+1,:] + 1) * s[i,:]

print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
A=[[] for i in range(n)]
node=[0]*n

for i in range(n-1):
    a,b=map(int,input().split())
    a -=1;b -=1
    A[a].append(b)
    A[b].append(a)

for i in range(q):
    p,x=map(int,input().split())
    node[p-1] +=x


def calculate(num,pre=-1):
    for i in A[num]:
        if i==pre:continue
        node[i] +=node[num]
        calculate(i,num)


calculate(0)
print(*node)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

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

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

def func(Bs):
    for x in range(N):
        if Bs[x] >= 0: continue
        if max(Bs[x::x + 1]) <= 0:
            Bs[x] = 0

func(As)

memo = {}
memo[tuple(As)] = sum(As)

cs = [i for i, A in enumerate(As) if A < 0]
for c in cs:
    for tupleA in list(memo.keys()):
        if tupleA[c] == 0:
            continue

        listA = list(tupleA)
        for x in range(c, N, c + 1):
            listA[x] = 0

        func(listA)
        memo[tuple(listA)] = sum(listA)

print(max(memo.values()))


### FIXED CODE ###

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

def func(Bs):
    for x in range(N):
        if Bs[x] >= 0: continue
        if max(Bs[x::x + 1]) <= 0:
            Bs[x] = 0

func(As)

zs = [27, 29, 31, 33] + list(range(34, 51))
for x in zs:
    if sum(As[x - 1::x]) < 0:
        for i in range(x - 1, N, x):
            As[i] = 0

ns = [1, 2, 4, 8, 16, 32] + [3, 6, 9, 12, 18, 24, 27, 36, 48] \
    + [5, 10, 15, 20, 25, 30, 40, 45, 50] + [7, 14, 21, 28, 35, 42, 49] \
    + [11, 22, 33, 44] + [13, 26, 39] + [17, 34] + [19, 38] + [23, 46] \
    + [29, 31, 37, 41, 43, 47]

memo = {}
memo[tuple(As)] = sum(As)

cs = [n - 1 for n in ns if n <= N and n not in zs and As[n - 1] < 0]
for c in cs:
    for tupleA in list(memo.keys()):
        if tupleA[c] == 0:
            continue

        listA = list(tupleA)
        for x in range(c, N, c + 1):
            listA[x] = 0

        func(listA)
        memo[tuple(listA)] = sum(listA)

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

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

l=[]
for s in a:
    for t in b:
        l.append(s+t)
l.sort()
l.reverse()
m=l[:k]
n=[]
for s in m:
    for t in c:
        n.append(s+t)
n.sort()
n.reverse()
for i in range(k):
    print(n[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

l=[]
for s in range(x):
    for t in range(y):
        for u in range(z):
            if (s+1)*(t+1)*(u+1)<= k:
                l.append(a[s]+b[t]+c[u])
            else:
                break
l.sort(reverse=True)
for i in range(k):
    print(l[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
inf = 10**15
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                d[b] = max(d[b], d[a]+c)
            else:
                d[b] = d[a] + c

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                updated[b] = True
        if updated[a]:
            updated[b] = True

if updated[n-1]:
    print("inf")
else:
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

ea = []
eb = []
cost = []

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    ea.append(a)
    eb.append(b)
    cost.append(-c)

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            update = True
    if not update:
        break

ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            if not negative[b]:
                update = True
            negative[b] = True
        if negative[a] and not negative[b]:
            negative[b] = True
            update = True
    if not update:
        break
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)
### BUGGY CODE ###

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


root = [0] + A + [0]
# check
for ind in range(1, N + 1):
    target = [r for i, r in enumerate(root) if i != ind]
    res = sum([abs(target[i] - target[i + 1]) for i in range(N)])
    print(res)

### FIXED CODE ###

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

full_root = [0] + A + [0]
full_place = [abs(full_root[i] - full_root[i + 1]) for i in range(N + 1)]
full_res = sum(full_place)
# check
for ind in range(1, N + 1):
    res = full_res - sum(full_place[ind - 1:ind + 1]) + abs(full_root[ind - 1] - full_root[ind + 1])

    print(res)
### BUGGY CODE ###

n,m=map(int,input().split())
lists_A=sorted(list(map(int,input().split())))
lists_BC=[]
sumk=0
for _ in range(m):
    k,l=map(int,input().split())
    sumk+=k
    
    lists_BC=lists_BC+[l]*k
lists_BC=sorted(lists_BC)
listsBC=lists_BC[-min(n,sumk):]
listsBC=sorted(listsBC,reverse=True)

#listsBCの左のタプルから順にlistsAについて適用していく。
#listA内のインデックス
indexcheck=0
tupleindex=0
maxi=sum(lists_A)
for _ in range(min(n,sumk)):
    a=maxi+listsBC[_]-lists_A[_]
    if a>maxi:
        maxi=a
    else:
        continue
        
print(maxi)
    

### FIXED CODE ###

n,m=map(int,input().split())
lists=list(map(int,input().split()))
checklist=[]
count=0

for i in range(m):
    b,c=map(int,input().split())
    checklist.append((c,b))
checklist=sorted(checklist,reverse=True)
lists=sorted(lists)
uselist=[]
count=0

for i in checklist:
    for _ in range(i[1]):
        uselist.append(i[0])
    count+=i[1]

    if count>=n:
        break
answer=0
n=min(n,len(uselist))
for i in range(n):
    if lists[i]<uselist[i]:
            lists[i]=uselist[i]
    else:
        break
print(sum(lists))
### BUGGY CODE ###

n,s = list(map(int,input().split())); arr = list(map(int,input().split()))

mod = 998244353
ans = 0
dp = [0]*(s+1)

for i in range(n):
    dp[0] += 1
    tmp = arr[i]
    for j in range(s,tmp-1,-1):
        dp[j] += dp[j-tmp]
        dp[j] %= mod
    ans += dp[s]
    ans %= mod
print(ans)

### FIXED CODE ###

n,s = list(map(int,input().split())); arr = list(map(int,input().split()))

mod = 998244353
ans = 0
dp = [0]*(s+1)

for i in range(n):
    dp[0] += 1
    tmp = arr[i]
    for j in range(s,tmp-1,-1):
        dp[j] += dp[j-tmp]
    ans += dp[s]
    ans %= mod
print(ans)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline

N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0

t = [(e, i) for i, e in enumerate(h, 0)]
heapify(t)
while t:
    g, i = heappop(t)
    # print(h, (g, i), v)
    if g > 1:
        heappush(t, (h[i], i))
    elif g == 1:
        v[i] = c[cur]
        h[i] -= 1
        for nv in es[i]:
            h[nv] -= 1
        cur += 1
# print(h, (g, i), v)
ans = sum(c) - c[-1]
print(ans)
v = [vv if vv != -1 else c[-1] for vv in v]
print(' '.join(map(str, v)))


### FIXED CODE ###

N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0
ans = 0
for _ in range(N - 1):
    for target in range(N):
        # print(target, h, v, ans)
        if h[target] == 1:
            h[target] = 0
            v[target] = c[cur]
            ans += c[cur]
            cur += 1
            for nv in es[target]:
                h[nv] -= 1
            break
for target in range(N):
    if v[target] == -1:
        v[target] = c[cur]
print(ans)
print(*v, sep='\n')
### BUGGY CODE ###

n = int(input())
sqrtN = n**(1/2)
if sqrtN.is_integer():
    Pos = [int(sqrtN), int(sqrtN)]
else:
    for i in range(int(sqrtN), n+1):
        if n%i == 0:
            Pos = [i, n//i]
            break
print(sum(Pos) - 2)

### FIXED CODE ###

n = int(input())
sqrtN = n**(1/2)
if sqrtN.is_integer():
    Pos = [int(sqrtN), int(sqrtN)]
#    print(Pos)
else:
    for i in range(int(sqrtN), 0, -1):
#        print(i)
        if n%i == 0:
            Pos = [i, n//i]
#            print(Pos)
            break
print(sum(Pos) - 2)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
c = tuple(map(int, input().split()))

ab = [i + j for i in a for j in b]
ab.sort(reverse=True)
abc = [i + j for i in ab[:k] for j in c]

abc.sort(reverse=True)
print("\n".join(map(str, abc[:k])))


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ab = ab[:k]

abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
        
abc.sort(reverse=True)
for i in abc[:k]:
    print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
list = []
i = 0
j = 0
while i not in list and j < K:
    list.append(i)
    i = X[i] - 1
    j += 1

if K == j:
    print(i+1)

else:    
    loop = j - list.index(i)
    print(list[(K - list.index(i)) % loop + list.index(i)]+1)


### FIXED CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
town = []
dic = {}
i = 0
j = 0
while i not in dic and j < K:
    dic[i] = j
    town.append(i)
    i = X[i] - 1
    j += 1

if j == K:
    print(i + 1)

else:
    num = dic[i]
    loop = j - num
    print(town[((K - num) % loop) + num] + 1)
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
for i in range(N, -1, -1):

    # 子ノードのdequeを集める
    R = None
    for j in G[i]:
        S = Q[j]
        if not R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # dequeの小さい方から大きい方へマージする処理
        for s, r in zip(S, R):
            a0, a1, a2, c0 = s
            b0, b1, b2, c1 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD
            r[3] = c0+c1
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        R.appendleft([1, 1, 0, 1])
        Q[i] = R
    else:
        Q[i] = deque([[1, 1, 0, 1]])
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)


### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
s=0
for i in range(n-1):
    for j in range(i, n):
        s+=a[i]^a[j]
print(s%1000000007)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(60):
  tmp = sum([1 for j in a if (j>>i)&1])
  ans += tmp*(n-tmp)*(2**i)
  ans %= 10**9+7
print(ans)
### BUGGY CODE ###

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

numlist=[]

while len(numlist) <=N:
    for i in range(A):
        numlist.append(1)
    for i in range(B):
        numlist.append(0)
ans= 0
for i in range(N):
    if numlist[i] == 1:
        ans +=1
    else:
        continue
print(ans)

### FIXED CODE ###

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

a = N//(A+B)
b = N%(A+B)

if b>A:
    print(a*A+A)
else:
    print(a*A+b)
### BUGGY CODE ###

length=int(input())
list=list(map(int,input().split()))
list.sort()
max=list[-1]
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        for i in range(max//num+1):
            dp[num*i]=False
        if list.count(num)==1:
            ret=ret+1
print(ret)


### FIXED CODE ###

import numpy as np
from collections import Counter

length=int(input())
list=list(map(int,input().split()))
list.sort()

max=list[-1]
dp=[0]*(max+1)
dp=np.array(dp,int)

for num in list:
    dp[num]=1

for num in list:
    if dp[num]==1:
        dp[2*num::num]=0

count=Counter(list)

for num,cnt in count.items():
    if cnt>1:
        dp[num]=0

print(dp.sum())
### BUGGY CODE ###

# import itertools
# import pprint
# import copy
# from collections import deque

h,w   = map(int,input().split())
mp    = list(list(input()) for i in range(h))
scx   = [[0 for _ in range(w)] for _ in range(h)]
scy   = [[0 for _ in range(w)] for _ in range(h)]
donex = [[0 for _ in range(w)] for _ in range(h)]
doney = [[0 for _ in range(w)] for _ in range(h)]
sc    = 0
ans   = 0

for y in range(h):
  for x in range(w):
    if mp[y][x]=='#':
      scx[y][x]==0
    elif donex[y][x]==1:
      continue
    else:
      l = 1
      while(x+l<w):
        if mp[y][x+l]=='#':
          break
        l += 1
      for i in range(l):
        scx[y][x+i] = l
        donex[y][x+i] = 1

for y in range(h):
  for x in range(w):
    if mp[y][x]=='#':
      scy[y][x]==0
    elif doney[y][x]==1:
      continue
    else:
      l = 1
      while(y+l<h):
        if mp[y+l][x]=='#':
          break
        l += 1
      for i in range(l):
        scy[y+i][x] = l
        doney[y+i][x] = 1

for y in range(h):
  for x in range(w):
    ans = max(ans, (scy[y][x] + scx[y][x] - 1))

print(ans)

### FIXED CODE ###

# import itertools
# import pprint
# import copy
# from collections import deque

h,w   = map(int,input().split())
mp    = list(list(input()) for i in range(h))
scx   = [[0 for _ in range(w)] for _ in range(h)]
scy   = [[0 for _ in range(w)] for _ in range(h)]
donex = [[0 for _ in range(w)] for _ in range(h)]
doney = [[0 for _ in range(w)] for _ in range(h)]
sc    = 0
ans   = 0

for y in range(h):
  for x in range(w):
    if mp[y][x]=='#':
      scx[y][x]==0
    elif donex[y][x]==1:
      continue
    else:
      l = 1
      while(x+l<w):
        if mp[y][x+l]=='#':
          break
        l += 1
      for i in range(l):
        scx[y][x+i] = l
        donex[y][x+i] = 1

for y in range(h):
  for x in range(w):
    if mp[y][x]=='#':
      scy[y][x]==0
    elif doney[y][x]==1:
      continue
    else:
      l = 1
      while(y+l<h):
        if mp[y+l][x]=='#':
          break
        l += 1
      for i in range(l):
        scy[y+i][x] = l
        doney[y+i][x] = 1

for y in range(h):
  for x in range(w):
    ans = max(ans, (scy[y][x] + scx[y][x] - 1))

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

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
    if l[i][0]>l[i][1]:
        l[i][0],l[i][1]=l[i][1],l[i][0]
l.sort()
r=[0]*(n-1)
for i in range(m):
    for j in range(l[i][0]-1,l[i][1]-1):
        r[j]+=1
#print(r,l)
for i in range(n-1):
    if r[i]%2==1:
        print('NO')
        break
else:
    print('YES')


### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
a=[0]*n
for i in range(m):
    a[l[i][0]-1]+=1
    a[l[i][1]-1]+=1
for i in range(n):
    if a[i]%2==1:
        print('NO')
        break
else:
    print('YES')
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for j in range(l-1,r-1):
        if s[j]=="A" and s[j+1]=="C":
            ans += 1
    print(ans)
            

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
    
ans = 0
ls = [0]
for i in range(len(s)-1):
    if s[i] == "A" and s[i+1] == "C":
        ans += 1
        ls.append(1+ls[i-1])
    else:
        ls.append(ls[i])
        
for i in range(q):
    l,r = map(int,input().split())
    print(ls[r-1]-ls[l-1])
### BUGGY CODE ###

import copy

N, M = map(int, input().split())
ans = [0]*(N+1)

path = []
check = []
for neveruse in range(M):
    l = list(map(int, input().split()))
    if 1 in l:
        temp = copy.copy(l)
        temp.remove(1)
        ans[temp[0]] = 1
        check.append(temp[0])
    else:
        path.append(l)

while len(check) > 0:
    precheck = copy.copy(check)
    check = []
    for n in precheck:
        for item in path:
            if n in item:
                tmpl = copy.copy(item)

                tmpl.remove(n)

                if ans[tmpl[0]] == 0:
                    ans[tmpl[0]] = n
                    check.append(tmpl[0])

ans.pop(1)

if ans.count(0) > 1:
    print('No')

else:
    ans[0] = 'Yes'

    for i in range(N):
        print(ans[i])

### FIXED CODE ###

N, M = map(int, input().split())

dist = [-1] * (N+1)
dist[1] = 0
connection = [[] for _ in range(N+1)]
ans = [-1] * (N+1)

for quel in range(M):
    a, b = map(int, input().split())
    connection[a].append(b)
    connection[b].append(a)

que = []
que.append(1)

while que:
    v = que.pop(0)

    for i in connection[v]:
        if dist[i] != -1:continue

        dist[i] = dist[v] + 1
        que.append(i)
        ans[i] = v

#print(dist)
print('Yes')
for j in range(2, N+1):
    print(ans[j])
### BUGGY CODE ###

n, w = map(int, input().split())
x = []
y = []

for i in range(n):
  a,b = map(int, input().split())
  x.append(b)
  y.append(a)

dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
  for j in range(w + 1):
    if(j >= y[i]):
      dp[i + 1][j] = max(dp[i][j], dp[i][j - y[i]] + x[i])
    else:
      dp[i + 1][j] = dp[i][j]

print(dp[n][w])


### FIXED CODE ###

n, w = map(int, input().split())
x = []
y = []

for i in range(n):
  a,b = map(int, input().split())
  x.append(b)
  y.append(a)

dp = [[0] * (w + 1) for i in range(n + 1)]

for i in range(n):
  for j in range(w + 1):
    if(j >= y[i]):
      dp[i + 1][j] = max(dp[i][j], dp[i][j - y[i]] + x[i])
    else:
      dp[i + 1][j] = dp[i][j]

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

def z_array(pattern, text):
    psize = len(pattern)
    tsize = len(text)
    str = pattern + '$' + text
    matchsize = 0
    for i in range(tsize-1):
        j = 0
        while (j <= psize - 1 and i+j <= tsize - 1 and str[j] == str[i+psize+1+j]):
            j += 1
        if(matchsize < j): matchsize = j
    return matchsize

def main(size, text):
    length = 0
    for i in range(size-1):
        z = z_array(text[i+1:size], text[:i+1])
        if(length < z): length = z
    return length

size = int(input())
text = input()
print(main(size, text))

### FIXED CODE ###

def main(size, text):
    pattern = ""
    matchlen = 0

    for i in range(size):
        pattern += text[i]
        while (len(pattern) > 0 and len(pattern) <= len(text[i+1:])):
            if pattern in text[i+1:]:
                matchlen = max(matchlen, len(pattern))
                break
            else:
                pattern = pattern[1:]
    
    return matchlen

if __name__ == '__main__':
    N = int(input())
    S = input()
    print (main(N, S))