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

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

end_list = list(filter(lambda x: x[1] == N, ab_list))

res = False

for end in end_list:
    if end[0] == 1:
        res = True
        break

if not res:
    for end in end_list:
        if len(list(filter(lambda x: (x[1] == end[0]) and (x[0] == 1), ab_list))) > 0:
            res = True
            break


if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")



### FIXED CODE ###

N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

if N - 1 in ends:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
s = input()
r = 0
if n > 2:
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                r += 1 if j - i != k - j and s[i] != s[j] and s[i] != s[k] and s[j] != s[k] else 0
print(r)

### FIXED CODE ###

n = int(input())
s = input()
r = 0
if n > 2:
    r = s.count('R') * s.count('G') * s.count('B')
    for i in range(n - 2):
        k = i + 2
        for j in range(i + 1, n - 1):
            k += 2 if j > i + 1 else 0
            if k >= n:
                break
            r -= 1 if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] else 0
print(r)
### BUGGY CODE ###

import heapq
import sys
from itertools import accumulate

input = sys.stdin.readline

def main():
    X, Y, A, B, C = map(int, input().split())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    R = list(map(int, input().split()))
    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)
    P_acc = [0] + list(accumulate(P))
    Q_acc = [0] + list(accumulate(Q))
    R_acc = [0] + list(accumulate(R))
    ans = 0
    for i in range(X+1):
        tmp = 0
        red = i
        tmp += P_acc[red]
        if C < X - i:
            continue
        no_color = X - i
        tmp += R_acc[X-i]
        blue = Q_acc[Y]
        b_h = Q[:Y]
        heapq.heapify(b_h)
        for j in range(X-i,C):
            a = heapq.heappop(b_h)
            if R[j] > a:
                heapq.heappush(b_h, R[j])
                blue -= a
                blue += R[j]
            else:
                break
        tmp += blue
        ans = max(ans, tmp)

    print(ans)







if __name__ == "__main__":
    main()

### FIXED CODE ###

import heapq
import sys
from itertools import accumulate
from collections import defaultdict

input = sys.stdin.readline

def main():
    X, Y, A, B, C = map(int, input().split())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    R = list(map(int, input().split()))
    ans = 0
    P_d = defaultdict(int)
    Q_d = defaultdict(int)
    R_d = defaultdict(int)

    for i in range(len(P)):
        P[i] = -P[i]
        P_d[P[i]] += 1
        
    for i in range(len(Q)):
        Q[i] = -Q[i]
        Q_d[Q[i]] += 1

    
    for i in range(len(R)):
        R[i] = -R[i]
        R_d[R[i]] += 1

    H = P + Q + R
    heapq.heapify(H)
    red = 0
    green = 0
    nocl = 0
    ans = 0
    for i in range(A + B + C):
        tmp = heapq.heappop(H)
        if red + green + nocl == X + Y:
            print(-ans)
            exit()

        if P_d[tmp] >= 1 and red < X:
            P_d[tmp] -= 1
            red += 1
            ans += tmp
        elif Q_d[tmp] >= 1 and green < Y:
            Q_d[tmp] -= 1
            green += 1
            ans += tmp
        elif R_d[tmp] >= 1:
            R_d[tmp] -= 1
            nocl += 1
            ans += tmp
    





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

n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = [False] * (n+1)
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n+1):
    if cursor[i] < n-1:
      j = table[i][cursor[i]]
      if not is_matched[i] and table[j][cursor[j]] == i and not is_matched[j]:
        match += 1
        cursor[i] += 1
        is_matched[i] = True
        cursor[j] += 1
        is_matched[j] = True
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched =  [False] * (n+1)
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)
### BUGGY CODE ###

import math
N = int(input())
for n in range(1,N+1):
    r_n = math.floor(math.sqrt(n))
    count = 0
    for x in range(1,r_n):
        for y in range(1,r_n):
            for z in range(1,r_n):
                if (x*x + y*y + z*z + x*y + y*z + z*x) == n:
                    count+=1
    print(count)

### FIXED CODE ###

import math
N = int(input())
ans = [0 for _ in range(10050)]
r_n = math.floor(math.sqrt(N))
count = 0
for x in range(1,r_n):
    for y in range(1,r_n):
        for z in range(1,r_n):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n < 10050:
                ans[n]+=1
for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

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

A.sort()
A.reverse()

list = []
ans = 0
list.append(A[0])
for i in range(1, len(A)):
        ans += list[0]
        list.pop(0)
        list.append(A[i])
        list.append(A[i])

print(ans)

### FIXED CODE ###

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

A.sort()
A.reverse()

list = []
ans = 0
list.append(A[0])
for i in range(1, len(A)):
        ans += list[i - 1]
        list.append(A[i])
        list.append(A[i])

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

def solve(node):
    global ans
    for i in range(N-1, 0, -1):
        s = 0
        maxi = 0
        num = len(paths[i])-1

        for to in paths[i]:
            s += dp[to]
            if(maxi<dp[to]):
                maxi=dp[to]
        if(i == node and num >= 2):
            num -= 1
            s -= maxi
        
        dp[i] = s / num + 1
    if(ans>dp[1]):
        ans = dp[1]


N, M = map(int, input().split())
paths = [[0]for j in range(N + 1)]
dp = [0 for i in range(N+1)]
ans = 1e12
for i in range(M):
    s, t = map(int, input().split())
    paths[s].append(t)
for i in range(N):
    solve(i)
print(ans)

### FIXED CODE ###

def solve(node):
    global ans
    for i in range(N-1, 0, -1):
        s = 0
        maxi = 0
        num = len(paths[i])-1

        for to in paths[i]:
            s += dp[to]
            if(maxi<dp[to]):
                maxi=dp[to]
        if(i == node and num >= 2):
            num -= 1
            s -= maxi
        
        dp[i] = s / num + 1
    if(ans>dp[1]):
        ans = dp[1]


N, M = map(int, input().split())
paths = [[0]for i in range(N + 1)]
dp = [0 for i in range(N+1)]
ans = 1e12
for i in range(M):
    s, t = map(int, input().split())
    paths[s].append(t)
for i in range(N):
    solve(i)
print(ans)
### BUGGY CODE ###

N = int(input())
s = []
for i in range(N):
    s.append(sorted(list(input())))

ans = 0
for i in range(N):
    for j in range(N):
        if not i == j:
            if (s[i] == s[j]):
                ans += 1
print(int(ans/2))

### FIXED CODE ###

N = int(input())
s = []
ans = 0
mydict = {}
for i in range(N):
    s = "".join(sorted(list(input())))
    if (s in mydict.keys()):
        ans += mydict[s]
        mydict[s] += 1
    else:
        mydict[s] = 1
print(ans)
### BUGGY CODE ###

from collections import deque
X, Y = map(int,input().split())
ans = 0
start = [0, 0]
move = [[1, 2], [2, 1]]
queue = deque()
queue.append(start)
while queue:
  x, y = queue.popleft()
  for i in range(len(move)):
    nextX = x + move[i][0]
    nextY = y + move[i][1]
    if nextX == X and nextY == Y:
      ans += 1
    if nextX < X and nextY < Y:
      queue.append([nextX, nextY])
print(ans%(10**9+7))


### FIXED CODE ###

X, Y = map(int,input().split())
n = int((2*Y-X)/3)
m = int((2*X-Y)/3)
if (X+Y)%3!=0:
  print(0)
  exit()
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10 ** 9 + 7
N = 10 ** 6  
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
print(cmb(n+m, n, p))
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
rinsetu = [set() for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, (input().split()))
    rinsetu[a].add(b)
    rinsetu[b].add(a)

grp = 0
color = ["white"] * (N + 1)
color[0] = "black"
for i in range(1, N + 1):
    if color[i] == "white":
        d = deque()
        d.append(i)
        a = set()
        a.add(i)
        while (d):
            k = d.popleft()
            color[k] = "black"
            for j in rinsetu[k]:
                if color[j] == "white":
                    d.append(j)
                    a.add(j)
        grp=max(grp,len(a))
print(grp)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
rinsetu = [set() for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, (input().split()))
    rinsetu[a].add(b)
    rinsetu[b].add(a)

grp = 0
color = ["white"] * (N + 1)
color_2 = ["white"] * (N + 1)
color[0] = "black"
for i in range(1, N + 1):
    count=1
    if color[i] == "white":
        d = deque()
        d.append(i)
        a = set()
        a.add(i)
        while (d):
            k = d.popleft()
            color[k] = "black"
            color_2[k]="black"
            for j in rinsetu[k]:
                if color[j] == "white" and color_2[j]=="white":
                    color_2[j]="black"
                    d.append(j)
                    count+=1
        grp=max(grp,count)
print(grp)
### BUGGY CODE ###

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

div=10**9+7
n=1
m=1
diff=abs(N-M)
for i in range(1,N+1):
    n*=i%div
for i in range(1,M+1):
    m*=i%div

if diff>1:
    ans=0
elif diff==0:
    ans=(2*n*m)%div
elif diff==1:
    ans=(n*m)%div
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
nn = 1
mm = 1
for i in range(1, N + 1):
  nn = (nn * i) % MOD
for j in range(1, M + 1):
  mm = (mm * j) % MOD
if abs(N - M) >= 2:
  ans = 0
elif abs(N - M) == 1:
  ans = (nn * mm) % MOD
else:
  ans = (2 * nn * mm) % MOD
print(ans)
### BUGGY CODE ###

# cook your dish here
n=int(input())
a=list(map(int,input().split()))
res=1
if 0 in a:
    print("0")
else:
    for i in a:
        res=res*i
    if(res>1000000000000000000):
        print("-1")
    else:
        print(res)

### FIXED CODE ###

def sol():
    n=int(input())
    a=list(map(int,input().split()))
    if 0 in a:
        print(0)
        return
    prod=1 
    for i in a:
        prod*=i 
        if prod>1000000000000000000:
            print(-1)
            return
    print(prod)
    
sol()
### BUGGY CODE ###

import numpy as np

n = int(input())
table = np.ones(n + 1, dtype=int)
multiple = np.arange(n + 1)

for i in range(2, n + 1):
  for j in range(i, n + 1, i):
    table[j] += 1
    
print(table @ multiple)

### FIXED CODE ###

n = int(input())

ans = 0
for i in range(1, n + 1):
  k = n // i
  ans += i * k * (k + 1) // 2
print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(sorted(list(map(int,input().split()))))

if 1 in A:
  A = np.delete(A,np.where((A%1==0) & ((A!=1) | (2<=len(np.where(A==1)[0])))))
if 2 in A:
  A = np.delete(A,np.where((A%2==0) & ((A!=2) | (2<=len(np.where(A==2)[0])))))

for a in A:
  A = np.delete(A,np.where((A%a==0) & ((A!=a) | (2<=len(np.where(A==a)[0])))))

print(len(A))

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())))
B = (10**6+1)*[0]

for a in A:
  B[a]+=1
  if B[a]==1:
    for n in range(2*a,10**6+1,a):
      B[n]+=10

print(B.count(1))
### BUGGY CODE ###

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

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        s = s[::-1]
    else:
        if t[1] == "1":
            s = t[2] + s
        else:
            s = s + t[2]

print(s)

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

rev = False

for _ in range(q):
    t = [x for x in input().split()]
    if t[0] == "1":
        rev = not rev
    else:
        if t[1] == "1":
            s.append(t[2]) if rev else s.appendleft(t[2])
        else:
            s.appendleft(t[2]) if rev else s.append(t[2])

if rev:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

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

MOD = 10**9 + 7

dig = 60
Abn = [[0]*dig for _ in range(n)]

for i in range(n):
  for j in range(dig):
    if A[i]>>j&1:
      Abn[i][j] = 1
      

Cbn = [[[0]*2 for j in range(dig)] for i in range(n)]

for j in range(dig):
  if Abn[n-1][j]==1:
    Cbn[n-1][j][1] = 1
  else:
    Cbn[n-1][j][0] = 1
    
for i in range(n-2, 0, -1):
  for j in range(dig):
    if Abn[i][j]==1:
      Cbn[i][j][0] = Cbn[i+1][j][0]
      Cbn[i][j][1] = Cbn[i+1][j][1] + 1
    else:
      Cbn[i][j][0] = Cbn[i+1][j][0] + 1
      Cbn[i][j][1] = Cbn[i+1][j][1]

ans = 0
two = [pow(2, i, MOD) for i in range(dig)]

for i in range(n-1):
  for j in range(dig):
    if Abn[i][j] == 1:
      ans += Cbn[i+1][j][0] * two[j] % MOD
    else:
      ans += Cbn[i+1][j][1] * two[j] % MOD
    ans %= MOD
    
print(ans)


### FIXED CODE ###

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

MOD = 10**9 + 7

dig = 60
Abn = [[0]*dig for _ in range(n)]

b0 = [0]*dig
b1 = [0]*dig
for i in range(n):
  for j in range(dig):
    if A[i]>>j&1:
      b1[j] += 1
    else:
      b0[j] += 1
      
pow2 = [pow(2, i, MOD) for i in range(dig)]

ans = 0
for i in range(dig):
  ans += b1[i]*b0[i]*pow2[i]%MOD
  
print(ans%MOD)
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
B = []
for i in range(m):
    b,c = list(map(int, input().split()))
    B.extend([c]*b)
print(sum(sorted(A+B, reverse=True)[:len(A)]))

### FIXED CODE ###

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

B = [[] for _ in range(m)]
for i in range(m):
    B[i] = list(map(int, input().split()))
B.sort(key=lambda x: -x[1])

_A = []
cnt = 0
for i in range(m):
    _A.extend([B[i][1]]*B[i][0])
    cnt += B[i][0]
    if cnt > n:
        break
A += _A
A.sort(reverse=True)
print(sum(A[:n]))
### BUGGY CODE ###

import sys

x, y, z, k = map(int, sys.stdin.readline().split())

xlist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(x, k)]
ylist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(y, k)]
zlist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(z, k)]


anslist = [0]
for i in range(min(x, k)):
    for j in range(min(y, k)):
        for l in range(min(z, k)):
            anslist.append(xlist[i]+ylist[j]+zlist[l])

anslist = sorted(anslist, reverse=True)
for i in range(k):
    print(anslist[i])


### FIXED CODE ###

import sys

x, y, z, k = map(int, sys.stdin.readline().split())

xlist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(x, k)]
ylist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(y, k)]
zlist = sorted(list([int(i)
                     for i in sys.stdin.readline().split()]), reverse=True)[:min(z, k)]


anslist = [0]
for i in range(min(x, k)):
    for j in range(min(y, k)):
        for l in range(min(z, k)):
            if (i+1)*(j+1)*(l+1) <= k:
                anslist.append(xlist[i] + ylist[j] + zlist[l])
            else:
                break

anslist = sorted(anslist, reverse=True)
for i in range(k):
    print(anslist[i])
### BUGGY CODE ###

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

t=[P[0]]
ans=1
for n in range(1,N):
    if min(t) < P[n]:
        pass
    else:
        ans+=1
    t.append(P[n])
print(ans)

### FIXED CODE ###

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

m=P[0]
ans=1
for p in P:
    if m > p:
        ans+=1
        m=p
print(ans)
### BUGGY CODE ###


# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

for i in range(M):
    a, b, c = map(int, input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# print(dist)

ans = 0

for i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: # 各辺がどの異なる２点の最短経路にも含まれないかを調べる
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    # 一つでも最短経路に含まれていたならブレイク
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            # 全ての異なる２点間の最短経路に含まれていなかったら+1カウント
            ans += flag


print(ans)

### FIXED CODE ###

# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

for i in range(M):
    a, b, c = map(int, input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# print(dist)

ans = 0

for i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: # 各辺がどの異なる２点の最短経路にも含まれないかを調べる
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    # 一つでも最短経路に含まれていたならブレイク
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            # 全ての異なる２点間の最短経路に含まれていなかったら+1カウント
            ans += flag


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

import sys
import time

class Node:
    def __init__(self, key = None):
        self.key = key
        self.left = None
        self.right = None

def insert(key):
    global root
    z = Node(key)
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right

    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    else:
        return find(node.left, key) or find(node.right, key)

def inorderTreeWalk(node):
    if node:
        return inorderTreeWalk(node.left) + " " + str(node.key) + inorderTreeWalk(node.right)
    return ""

def preorderTreeWalk(node):
    if node:
        return " " + str(node.key) + preorderTreeWalk(node.left) + preorderTreeWalk(node.right)
    return ""

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            print inorderTreeWalk(root)
            print preorderTreeWalk(root)
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(int(com[1]))
            else:
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"

### FIXED CODE ###

import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    elif node.key > key:
        return find(node.left, key)
    else:
        return find(node.right, key)

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            else:
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"
### BUGGY CODE ###

class RollingHash:
    def __init__(self,text):
        self.mod=10**17+3
        self.p=10007
        self.n=len(text)
        self.table=[0]*(self.n+1)
        for i in range(self.n):
            self.table[i+1]=(self.table[i]*self.p+ord(text[i]))%self.mod
        self.pp=[1]*(self.n+1)
        for i in range(self.n):
            self.pp[i+1]=(self.pp[i]*self.p)%self.mod
    def hash(self, i, j):
        return (self.table[j]-self.table[i]*self.pp[j-i])%self.mod
    def lcp(self, i, j):
        l,r=0,min(self.n-i,self.n-j)+1
        while r-l>1:
            m=(l+r)//2
            if self.hash(i,i+m)==self.hash(j,j+m):
                l=m
            else:
                r=m
        return l

n=int(input())
hs=RollingHash(input())
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans=max(ans,min(j-i,hs.lcp(i,j)))
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
l=0
r=n//2
while r-l>=1:
    m=(r+l+1)//2
    d={}
    flg=False
    for i in range(n-m+1):
        t=s[i:i+m]
        if t in d:
            if d[t]+m-1<i:
                flg=True
                break
        else:
            d[t]=i
    if flg:
        l=m
    else:
        r=m-1
print(l)