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

from collections import Counter
n = int(input())
s = [input() for i in range(n)]
cnt = 0
for i in range(1,n):
    for l in range(i-1):
        if Counter(s[i]) == Counter(s[l]):
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    s = ''.join(sorted(input()))
    if s not in d:
        d[s] = 1
    else:
        d[s] += 1
cnt = [i*(i-1)//2 for i in d.values()]
print(sum(cnt))
### BUGGY CODE ###

import sys
import os

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

def main():
    #file_input()
    # input()
    A,B,N=map(int, input().split())

    max=0
    for x in range(N+1):
        ans=int(A*x/B)-A*int(x/B)
        if ans > max:
            max=ans

    print(max)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

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

def main():
   # file_input()
    # input()
    A,B,N=map(int, input().split())

    max=0
    # for x in range(N+1):
    #     # ans=int(A*x/B)-A*int(x/B)
    #     min,_=math.modf(x/B)
    #     # ans=int(A*min)
    #     # print(min)
    #     if x==0:
    #         max=min
    #     elif min > max:
    #         max=min
    #     else:
    #         break

    # max=0
    # max_x=0
    # first=0
    #
    # for x in range(N+1):
    #     rem = x%B
    #     if x == 0:
    #         first=rem
    #     elif rem == first:
    #         break
    #     if rem > max:
    #         max=rem
    #         max_x=x

    if N<B:
        max_x=N
    else:
        max_x=B-1

    # min,_=math.modf(max_x/B)

    print(int(A*max_x/B)-A*int(max_x/B))

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

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

B = []

if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.insert(0,A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.insert(0,A[i])
        else:
            B.append(A[i])

for i in B:
    print(i,end=' ')

print()


### FIXED CODE ###

from collections import deque

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

B = deque(maxlen=2*10**5)

if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])

print(*B)
### BUGGY CODE ###

h,w,m=map(int,input().split())
bomb=[list(map(int,input().split())) for _ in range(m)]
a=[0 for i in range(h+1)]
b=[0 for _ in range(w+1)]
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a)
bm=max(b)
aa=[i for i, x in enumerate(a) if x==am]
bb=[i for i, x in enumerate(b) if x==bm]
for i in aa:
    for j in bb:
        if [i,j] in bomb:
            continue
        else:
            print(am+bm)
            exit()
print(am+bm-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
bomb=[list(map(int,input().split())) for _ in range(m)] #bombの位置
a=[0 for i in range(h+1)] #各行のbombの個数
b=[0 for _ in range(w+1)] #各列のbombの個数
for i in range(m):
    a[bomb[i][0]]+=1
    b[bomb[i][1]]+=1
am=max(a) #１行にあるbombの最大値
bm=max(b) #１列にあるbombの最大値
hmax=[0]*(h+1) #最大値をとるh全部
wmax=[0]*(w+1) #最大値をとるw全部
for i in range(h+1):
    if am==a[i]:
        hmax[i]+=1
for i in range(w+1):
    if bm==b[i]:
        wmax[i]+=1
ans=am+bm #基本解
k=sum(hmax)*sum(wmax)
if k>m: #鳩ノ巣原理
    print(ans)
    exit()
for i in bomb:
    if hmax[i[0]]==1 and wmax[i[1]]==1:
        k-=1
if k==0:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for x in range(min(A), max(A)+1):
    ans = max(A.count(x - 1) + A.count(x) + A.count(x + 1), ans)
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
C = [0] * 100002
for x in A:
    for i in range(3):
        C[x + i] += 1
print(max(C))
### BUGGY CODE ###

p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            ans[j] %= p
# print(ans)
print(" ".join([str(item) for item in ans]))

### FIXED CODE ###

p = int(input())
a = [int(item) for item in input().split()]

fac = [1] + [0] * (p - 1)
facinv = [1] + [0] * (p - 1)
for i in range(1, p):
    fac[i] = fac[i-1] * i % p
    facinv[i] = facinv[i-1] * pow(i, p-2, p) % p

# print(fac)
# print(facinv)
comb = [0] * p
for i in range(p):
    comb[i] = fac[p-1] * facinv[i] * facinv[p-1-i] % p

# print(comb)
ans = [0] * p
ppowp = [[0] * (p + 1) for _ in range(p + 1)]
for i in range(p+1):
    val = 1
    for j in range(p+1):
        ppowp[i][j] = val
        val *= i
        val %= p

for i, item in enumerate(a):
    if item == 1:
        ans[0] += 1
        # Calc (i - x)**(p - 1) 
        for j in range(p):
            # ans[j] -= pow(i, p-1-j, p) * pow(-1, j, p) * comb[j] % p
            if j % 2 == 1:
                ans[j] -= ppowp[i][p-1-j] * -1 * comb[j] % p
            else:
                ans[j] -= ppowp[i][p-1-j] * comb[j] % p
            ans[j] %= p
print(" ".join([str(item) for item in ans]))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

a_max = max(A)

for i,a in enumerate(A):
    if a == a_max:
        A[i] -= a
        print(max(A))
        A[i] += a
    else:
        print(a_max)

### FIXED CODE ###

N = int(input())
A=[]
for _ in range(N):
    A.append(int(input()))
    
ref = sorted(A)

for x in A:
    if x == ref[-1]:
        print(ref[-2])
    else:
        print(ref[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
# 問題はM//N>xを満たすようなMの約数xの中で最小のものと読み替えられる。
bdr = M//N
ans = 1
for i in range(1,M):
    if M%i==0:
        if i<=bdr:
            ans = i
        if i>bdr:
            break
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
# 問題はM//N>xを満たすようなMの約数xの中で最小のものと読み替えられる。
bdr = M//N
ans = 1

for i in range(1,int(M**0.5+1)):
    if M%i==0:
        yakusu = M//i
        if yakusu<=bdr:
            ans = yakusu
            break
        elif i <= bdr:
            ans = i
print(ans)
### BUGGY CODE ###

from itertools import product
import numpy as np
H, W, K = map(int, input().split())
choko = np.array([list(input()) for _ in range(H)], dtype=int)

np.cumsum(choko, axis=1, out=choko)

ans = 10**18
for p in product(range(2), repeat=H - 1):
    Hcut = sum(p)

    ch = np.zeros((Hcut + 1, W), dtype=int)
    cnt = choko[0]
    h = 0
    for i, b in enumerate(p):
        if b:
            ch[h] = cnt
            cnt = choko[i + 1]
            h += 1
        else:
            cnt = cnt + choko[i + 1]
    ch[h] = cnt

    if (ch[:, 0] > K).any():
        continue

    Vcut = 0
    left = np.zeros(Hcut + 1, dtype=int)
    for i in range(W):
        right = ch[:, i]
        if (right - left > K).any():
            Vcut += 1
            left = ch[:, i - 1]
    ans = min(ans, Hcut + Vcut)

print(ans)

### FIXED CODE ###

from itertools import product, combinations_with_replacement
H, W, K = map(int, input().split())
S = tuple(tuple(map(int, list(input()))) for _ in range(H))

choko = [[0]*W for _ in range(H)]

ans = 10**18

for divide in product(range(2), repeat=H - 1):
    cut = sum(divide)
    row = [0]
    for d in divide:
        if d:
            row.append(row[-1] + 1)
        else:
            row.append(row[-1])

    r = row[-1] + 1
    for i in range(r):
        for j in range(W):
            choko[i][j] = 0
    for i in range(H):
        for j in range(W):
            choko[row[i]][j] += S[i][j]

    if any(choko[i][0] > K for i in range(r)):
        continue

    now = [0] * r
    for j in range(W):
        if any(now[i] + choko[i][j] > K for i in range(r)):
            cut += 1
            now = [choko[i][j] for i in range(r)]
        else:
            for i in range(r):
                now[i] += choko[i][j]

    ans = min(ans, cut)

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

import itertools

n=int(input())
a=list(map(int,input().split()))
l=[]
for i in range(1,n+1):
    l.append(i)
tmpList= (list([x,y] for x,y in (itertools.combinations(l, 2)) if x<y))
ans=0
for item in tmpList:
    if a[item[0]-1]!=item[0] and a[item[1]-1]!=item[1] and a[item[1]-1]==item[0] and a[item[0]-1]==item[1]:
        ans+=1
print (ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a = [None] + a
cnt = 0
for i in range(1, n):
  j = a[i]
  if j > i and a[j] == i:
    cnt += 1
print(cnt)
### BUGGY CODE ###

abm=(input().split(" "))
al1=(input().split(" "))
bl1=(input().split(" "))
minp=int(al1[0])+int(bl1[0])

for ai in al1:
    ai=int(ai)
    for bi in bl1:
        bi=int(bi)
        ci=ai+bi
        if minp>ci:
            minp=ci
for n in range(0,int(abm[2])):
    a,b,c = map(int,input().split())
    ci=int(al1[a-1])+int(bl1[b-1])-int(c)
    if minp>ci:
        minp=ci

print(minp)

### FIXED CODE ###

abm=(input().split(" "))
al1=list(map(int,input().split(" ")))
bl1=list(map(int,input().split(" ")))
#print(al1)
#print(bl1)
minp=min(al1)+min(bl1)


for n in range(0,int(abm[2])):
    a,b,c = map(int,input().split())
    ci=int(al1[a-1])+int(bl1[b-1])-int(c)
    if minp>ci:
        minp=ci

print(minp)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in [0]*n ]
# print(a)
s = set()
count = 0
c = -1
# for i in range(2):
while len(s)!=n:
	for i, t in enumerate(a) :
		# print(c)
		if i not in s:
			if c < t:
				c = t
				s.add(i)
		# print(t)
		# print(c)				
	count+=1
	# print(s)
	# print(count)
	c=-1
	
print(count)
# print(s)



### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[int(input()) for i in range(n)]
data=collections.deque()
for i, ai in enumerate(A):
    k=bisect.bisect_left(data,ai)
    if k==0:
        data.appendleft(ai)
    else:
        data[k-1]=ai
print(len(data))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
from math import inf


def bfs(maze, visited, Ch, Cw, Dh, Dw, H, W):
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x]
                    queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]

    dist = bfs(maze, visited, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)
    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[2, 2], [2, 1], [2, 0], [2, -1], [2, -2], [1, 2], [1, 1], [1, -1], [1, -2], [0, 2],
              [0, -2], [-1, 2], [-1, 1], [-1, -1], [-1, -2], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -2]]

    while queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

N=int(input())
S=input()
b=0
for i in range(1000):
 a=0
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 for j in range(N-2):
  if int(S[j])==i1:
   for k in range(j+1,N-1):
    if int(S[k])==i2:
     for l in range(k+1,N):
      if int(S[l])==i3:
       a+=1
     break
 if a>0:
  b+=1
print(b)


### FIXED CODE ###

N=int(input())
S=input()
A=[0]*N
for i in range(N):
 A[i]=int(S[i])
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if A[j]==i1:
    a+=1
  elif a==1:
   if A[j]==i2:
    a+=1
  else:
   if A[j]==i3:
    b+=1
    break
print(b)
### BUGGY CODE ###

N = int(input())

for n in range(1, N+1):
    s = n//5
    cnt = 0
    flag = 0

    for x in range(1, s+1):
        for y in range(x, s+1):
            for z in range(y, s+1):
                siki = x**2 + y**2 + z**2 + x*y + y*z + z*x
                f2 = 0
                if siki == n:
                    # print('ans = ', siki)
                    if (x==y)and(y==z):
                        cnt += 1
                    elif (x!=y)and(y!=z):
                        cnt += 6
                    else:
                        cnt += 3
                # elif siki > n:
                    flag = 1
                    break
                elif siki > n:
                    f2 = 1
                    # print('f2= ', f2)
                    # print('x,y,z= ',x,y,z)
                    break

            # if flag or f2>=2:
            if flag or (f2 and (z-y)==1):
                break
        # if flag or f2>=3:
        if flag or (f2 and (y-x)==1):
            break
    print(cnt)

### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(0,k+1):
    for j in range(0,k+1):
        for l in range(0,k+1):
            if i + j + l == s:
                ans += 1
print(ans)


### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(0,k+1):
    for j in range(0,k+1):
      if s - (i+j) >= 0 and s - (i+j) <= k:
        ans += 1
print(ans)
### BUGGY CODE ###

S = input()

L = 0
U = len(S)

while U - L > 1:
    M = (U + L) // 2

    OK = False
    for i in range(2):
        A = i
        B = M
        if A % 2 != B % 2: B -= 1

        NG = False
        for s in S:
            if s == '0':
                A -= 1
                B -= 1
            elif s == '1':
                A += 1
                B += 1
            else:
                A -= 1
                B += 1

            if A < 0: A += 2
            if B > M: B -= 2
            if A > B:
                NG = True
                break

        if not NG:
            OK = True
            break

    if OK:
        U = M
    else:
        L = M

print(U)


### FIXED CODE ###

S = input()

L = 0
U = len(S)

while U - L > 1:
    M = (U + L) // 2

    OK = False
    for i in range(2):
        A = i
        B = M
        if A % 2 != B % 2: B -= 1

        NG = False
        for s in S:
            if s == '0':
                A -= 1
                B -= 1
            elif s == '1':
                A += 1
                B += 1
            else:
                A -= 1
                B += 1

            if A < 0: A += 2
            if B > M: B -= 2
            if A > B:
                NG = True
                break

        if not NG:
            OK = True
            break

    if OK:
        U = M
    else:
        L = M

print(U)
### BUGGY CODE ###

def convertListToStr(lst):
	s = "".join(lst)
	return s

N=int(input())
dict={}
ans=0
for i in range(N):
	s = convertListToStr(sorted(input()))
	for check in dict:
		if check==s:
			ans+=dict[check]
			dict[check]+=1
			break
	else:
		dict[s]=1
print(ans)

### FIXED CODE ###

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

import math

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

for i in range(1, max_a):
    cnt = 0
    for a in A:
        cnt += math.ceil(a/i) - 1
    
    if cnt <= K:
        print(i)
        exit()
print(max_a)

### FIXED CODE ###

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

ng = 0
ok = max(A)

while ok - ng > 1:
    cnt = 0
    l = (ok + ng) // 2
    for a in A:
        cnt += (a // l) + (a % l != 0) - 1

    if cnt <= K:
        ok = l
    else:
        ng = l
print(ok)
### BUGGY CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	h = list(map(int, input().split()))
	# dpテーブル宣言: dp[今いる足場の番号-1]=最小コスト
	dp = [float('inf')] * N
	dp[0] = 0

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(1, N):
		dp[n] = min(
			[
				abs( h[n] - h[n-k-1] ) + dp[n-k-1]
				for k in range(min(n,K))]
		)
	print(dp[N-1])

resolve()

### FIXED CODE ###

def resolve():
	# N: 足場の個数, K: 1回で右にジャンプできる足場の数
	N, K = map(int, input().split())
	# h: 各足場の高さ
	# dpテーブル宣言: dp[今いる足場の番号-1]=[最小コスト, 足場の高さ]
	dp = [
		[float('inf'), int(h_)]
		for h_ in input().split()
	]
	dp[0][0] = 0
	dp[1][0] = abs(dp[0][1] - dp[1][1])

	# k個左の足場からジャンプして来た時の最小コストを調べる
	for n in range(2, N):
		index_0 = max(0, n-K)
		h_ = dp[n][1]
		dp[n][0] = min(
			[
				abs( h_ - dp_[1] ) + dp_[0]
				for dp_ in dp[index_0:n]
			]
		)
	print(dp[N-1][0])

resolve()
### BUGGY CODE ###

N,M=map(int,input().split())
key=[[] for _ in range(M)]
for i in range(M):
  A,B=map(int,input().split())
  key[i].append(A)
  C=list(map(int,input().split()))
  bit=0
  for c in C:
    bit+=2**(c-1)
  key[i].append(bit)

dp=[float("inf")]*(2**N)
dp[0]=0
ndp=[0]*(2**N)
for i in range(M):
  cost=key[i][0]
  bit=key[i][1]
  ndp=dp[:]
  for j in range(2**N):
  	ndp[bit|j]=min(dp[j]+cost,ndp[bit|j])
  dp=ndp[:]
 
print(dp[-1] if dp[-1]!=float("inf") else -1)
  

### FIXED CODE ###

N,M=map(int,input().split())
key=[[] for _ in range(M)]
for i in range(M):
  A,B=map(int,input().split())
  key[i].append(A)
  C=list(map(int,input().split()))
  bit=0
  for c in C:
    bit+=2**(c-1)
  key[i].append(bit)

dp=[float("inf")]*(2**N)
dp[0]=0
ndp=[0]*(2**N)
for i in range(M):
  cost=key[i][0]
  bit=key[i][1]
  ndp=dp[:]
  for j in range(2**N):
  	ndp[bit|j]=min(dp[j]+cost,ndp[bit|j])
  dp=ndp[:]
 
print(dp[-1] if dp[-1]!=float("inf") else -1)
### BUGGY CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = [0]
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop(0)
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = []
for i in range(q):
    lr.append([int(i) for i in input().split()])
    
acpos = []
for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        acpos.append(i)

for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1
    s_q = s[l-1:r]
    retSum = 0
    for j in range(len(acpos)):
        if l <= acpos[j] and r > acpos[j]:
            retSum +=1
        if r <= acpos[j]:
            break
    print(retSum)

### FIXED CODE ###

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

import numpy as np
N = int(input())
S = input()

def z_arr(s):
    Z = [0] * len(s)
    Z[0] = len(s)

    rt = 0
    lt = 0

    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.

            p = k - lt  # Pair index.
            right_part_len = rt - k + 1

            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k

                lt = k
                rt = i - 1
    return Z

ans = 0
for i in range(len(S)):
    x = z_arr(S[i:])
    for j,e in enumerate(x):
        remain_length = len(S[i:])-e
        if remain_length >= e:
            if e > ans:
                ans = e

print(ans)



### FIXED CODE ###

n = int(input())
s = input()
def output():
    left, right = 0, n//2+1
    while left < right-1:
        mid = (left+right)//2
        if check(mid):
            left = mid
        else:
            right = mid
    return left
def check(x):
    hashes = set()
    for i in range(n - 2*x + 1):
        hashes.add(s[i: i+x])
        if s[i+x: i+2*x] in hashes:
            return True
    return False
print(output())