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

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    def bfs(row, col, R, C, s):
        from collections import deque
        q = deque()
        q.append([(row, col), 0])
        seen = set()
        ans = 0
        while q:
            (r, c), dist = q.popleft()
            ans = max(dist, ans)
            seen.add((r, c))
            for (next_r, next_c) in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if 0 <= next_r < R and 0 <= next_c < C and \
                   (next_r, next_c) not in seen and \
                   s[next_r][next_c] == '.':
                    q.append([(next_r, next_c), dist + 1])
        return ans

    max_v = 0
    for h in range(H):
        for w in range(W):
            if s[h][w] == '.':
                max_v = max(max_v, bfs(h, w, H, W, s))
    print(max_v)
resolve()

### FIXED CODE ###

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    from collections import defaultdict
    cnt = defaultdict(int)
    for item in s:
        for c in item:
            cnt[c] += 1
    if '#' not in cnt:
        print(H+W-2)
        quit()

    def bfs(row, col, R, C, s):
        from collections import deque
        q = deque()
        q.append([(row, col), 0])
        seen = set()
        ans = 0
        while q:
            (r, c), dist = q.popleft()
            ans = max(dist, ans)
            seen.add((r, c))
            for (next_r, next_c) in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if (next_r, next_c) not in seen and \
                    0 <= next_r < R and 0 <= next_c < C and \
                   s[next_r][next_c] == '.':
                    q.append([(next_r, next_c), dist + 1])
        return ans

    max_v = 0
    for h in range(H):
        for w in range(W):
            if s[h][w] == '.':
                max_v = max(max_v, bfs(h, w, H, W, s))
    print(max_v)
resolve()
### BUGGY CODE ###



N = int(input())
S = []
Sset = set()
for i in range(N):
    s = input()
    Sset.add(s)
    S.append(s)



names = [0]*len(Sset)

for i, name in enumerate(Sset):
    cnt = 0
    for s in S:
        if(name==s):
            cnt += 1
            names[i] = (name, cnt)
max = 0
for n in names:
    if max<n[1]:
        max = n[1]
ans = []
for n in names:
    if n[1]==max:
        ans.append(n[0])

ans.sort()
for a in ans:
    print(a)


### FIXED CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import product, combinations,permutations
from copy import deepcopy
import sys
sys.setrecursionlimit(4100000)



if __name__ == '__main__':
    N = int(input())
    S_list = []

    s_hash = dict()

    for i in range(N):
        S_list.append(input())

    for s in S_list:
        if s not in s_hash:
            s_hash[s] = 1
        else:
            s_hash[s] += 1
    max_p = 0
    max_p_name = []
    for k, v in s_hash.items():
        if max_p < v:
            max_p_name = []
            max_p = v
        if max_p == v:
            max_p_name.append(k)
    
    for p in sorted(max_p_name):
        print(p)
### BUGGY CODE ###

import math
k = int(input())
t = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ab = math.gcd(a, b)
            d = math.gcd(ab, c)
            t += d

print(t)


### FIXED CODE ###

import math
k = int(input())
t = 0
# a = b = c
for x in range(1, k+1):
    t += x
# a = b != c
for a in range(1, k+1):
    for b in range(a+1, k+1):
        t += 6*math.gcd(a, b)
# a != b != c
for a in range(1, k+1):
    for b in range(a+1, k+1):
        for c in range(b+1, k+1):
            d = math.gcd(a, b)
            t += 6*math.gcd(d, c)
print(t)
### BUGGY CODE ###

import sys #追加
n=int(input())
sys.setrecursionlimit(10**6*2)

s=input()
X=int(s,2)
ans=[]


def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if x==0:
        return 0    
    else:
        if x%(str(bin(x)).count("1"))==0:
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=X
    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        #print(bin(tmp_num),n-i-1)
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)
            









### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)
### BUGGY CODE ###


A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    for i in range(2,n+1):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
#        else:
#            stop_flag = int(stop_flag/i) 
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

print(ans)


### FIXED CODE ###


A,B =[int(x) for x in input().split()]

def bunkai(n):
    sosu= {1}
    tmp = n
    stop_flag = n
    
    if tmp%2 == 0:
        while tmp%2==0:
            tmp //=2
        sosu.add(2)
    
    for i in range(3,n+1,2):
        if tmp%i == 0:
            while tmp%i==0:
                tmp //=i
            sosu.add(i)
            stop_flag = tmp 
            
        if i > stop_flag:
            break
        else:
            stop_flag = int(n/i)+1
            
    if tmp!=1:
        sosu.add(tmp)
                
    if sosu==[1]:
        sosu.add(n)
    
    return sosu

def check_sosu(n,x):
    ans=0
    tmp = n
    for i in x:
        if (tmp % i) == 0:
            ans+=1
    return ans

ans = check_sosu(B,bunkai(A))

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

import itertools
n = int(input())
l = list(map(int,input().split()))
ls = sorted(l, reverse = True)

count = 0
for i in range(n):
    x = ls[i]
    comb = list(itertools.combinations(ls[i+1:], 2))
    for j in range(len(comb)):
        if sum(comb[j]) > x:
            count += 1
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
ls = sorted(l)

count = 0
for i in range(n):
    for j in range(i+1, n):
        index = bisect.bisect_left(ls[j+1:], ls[i] + ls[j])
        count += index
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000000)

def main():
    N, Q = list(map(int, input().split()))
    graph = [[] for i in range(N)]
    # 最初にroot pointを定めて:
    # graph構造に大して点を与える...
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    points = [0] * N
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        points[p-1] += x
    
    visited = [False] * N
    
    nodes = graph[0]
    visited[0] = True
    
    
    def dfs(old_node, node):
        if visited[node]:
            return
        points[node] += points[old_node]
        visited[node] = True
        nodes = graph[node]
        [dfs(node, _node) for _node in nodes if not visited[_node]]

    for _node in nodes:
        dfs(0, _node)
    
    print(*points)
    
main()

### FIXED CODE ###

import sys
from queue import deque
input = sys.stdin.readline

def main():
    N, Q = list(map(int, input().split()))
    graph = [[] for i in range(N)]
    # 最初にroot pointを定めて:
    # graph構造に大して点を与える...
    for i in range(N-1):
        a, b = list(map(int, input().split()))
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    points = [0] * N
    for _ in range(Q):
        p, x = list(map(int, input().split()))
        points[p-1] += x
    
    visited = [False] * N
    
    nodes = deque([0])

    while nodes:
        node = nodes.pop()
        visited[node] = True
        for _node in graph[node]:
            if visited[_node]:
                continue
            points[_node] += points[node]
            nodes.append(_node)
    
    print(*points)
    
main()
### BUGGY CODE ###

def combine(a, j):
    # combine by xor all elements of a except a[j]
    x = 0
    n = len(a)
    for i in range(n):
        if i != j:
            x ^= a[i]
    return x

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    print(' '.join(str(combine(a, j)) for j in range(N)))


main()


### FIXED CODE ###

def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    x = 0
    for i in range(N):
        x ^= a[i]

    x ^= a[0]
    xors = [x]
    for i in range(1, N):
        x ^= a[i-1]
        x ^= a[i]
        xors.append(x)

    print(' '.join(str(x) for x in xors))


main()
### BUGGY CODE ###


def main():
  n = int(input())
  src = input()
  base_cnt = 0
  for bit in src:
    if bit == '1':
      base_cnt += 1
  base = int(src, 2)

  dp = [None] * n
  dp[0] = 0

  def popcount(num, cnt):
    if num < n and dp[num] is not None:
      return dp[num]

    if not cnt:
      cnt = 0
      for bit in format(num, 'b'):
        if bit == '1':
          cnt += 1

    res = 1 + popcount(num % cnt, None)
    if num < n:
      dp[num] = res

    return res

  for i in range(n - 1, -1, -1):
    num, cnt = (base + 2 ** i, base_cnt + 1) if src[n - i - 1] == '0' else (base - 2 ** i, base_cnt -1)
    print(popcount(num, cnt))


main()


### FIXED CODE ###


def f(n):
  cnt = 0
  while n:
      cnt += 1
      n = n % bin(n).count('1')

  return cnt

def main():
  n = int(input())
  src = input()
  base = int(src, 2)
  base_cnt = src.count('1')

  basep = base % (base_cnt + 1)
  basem = base % (base_cnt - 1) if base_cnt > 1 else 0

  for i, s in enumerate(src):
    i = n - 1 - i
    num = None

    if s == '0':
      mod = base_cnt + 1
      num = (basep + pow(2, i, mod)) % mod
    elif base_cnt > 1:
      mod = base_cnt - 1
      num = (basem - pow(2, i, mod)) % mod
    else:
      print(0)
      continue

    print(1 + f(num))


main()
### BUGGY CODE ###

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

count_min = x * a + y * b
for p_a in range(x + 1):
    for p_b in range(y + 1):
        if x - p_a == y - p_b:
            p_ab = max((x - p_a), (y - p_b)) * 2
            count = p_a * a + p_b * b + p_ab * c
            if count < count_min:
                count_min = count

print(count_min)

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())
 
ans_min = x * a + y * b
for i in range(100001):
    ans = i * 2 * c + max(0, x - i) * a + max(0, y - i) * b
    if ans < ans_min:
        ans_min = ans
 
print(ans_min)
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
n = int(input())
tree = defaultdict(list)
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

def distance(x, y):
    seen = set()
    d = 0
    stack = deque([[tree[x], d]])
    flag = True
    while flag:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                if i[0] == y:
                    flag = False
                    break
                stack.append([tree[i[0]], d])
                d -= i[1]
    return d

q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    print(distance(x, k) + distance(y, k))

### FIXED CODE ###

from collections import defaultdict
from collections import deque
n = int(input())
tree = defaultdict(list)
for i in range(n-1):
    a, b, c = map(int, input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

def distance(k):
    seen = set()
    dis_l = {}
    d = 0
    stack = deque([[tree[k], d]])
    flag = True
    while stack:
        connect, d = stack.popleft()
        for i in connect:
            if i[0] not in seen:
                seen.add(i[0])
                d += i[1]
                dis_l[i[0]] = d
                stack.append([tree[i[0]], d])
                d -= i[1]
    return dis_l

q, k = map(int, input().split())
dis_l = distance(k)
for i in range(q):
    x, y = map(int, input().split())
    print(dis_l[x] + dis_l[y])
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
x = float("inf")

dp = [x] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))

print(dp[n - 1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
x = float("inf")

dp = [x] * n
dp[0] = 0
for i in range(1, n):
    for j in range(max(0, i - k), i):
        dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))

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


def main():
    a = input()
    array = list(map(int, input().split()))

    sum = 1
    for i in range(len(array)):
        sum *= array[i]

    if (sum > 10**18):
        sum = -1;

    print(sum)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    a = input()
    array = list(map(int, input().split()))

    sum = 1

    new_array = sorted(array)
    for i in range(len(new_array)):
        sum *= new_array[i]
        if (sum > 10**18 or sum == 0):
            break

    if (sum > 10**18):
        sum = -1

    print(sum)

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

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
count = 0
suma = sum(a)
dp = [[0] * (suma+1) for i in range(N)]
dp[0][0] = 2
dp[0][a[0]] = 1
allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	for j in range(sum(a[:i+1])+1):
		if(j < k):
			dp[i][j] = dp[i-1][j]*2
		else:
			dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
allc = allc - sum(dp[N-1][suma-suma/2:])*3
if(suma%2 == 0):
	dp2 = [[0] * (suma+1) for i in range(N)]
	dp2[0][0] = 1
	dp2[0][a[0]] = 1 
	for i in range(1,N):
		k = a[i]
		for j in range(sum(a[:i+1])+1):
			if(j < k):
				dp2[i][j] = dp2[i-1][j]
			else:
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
	allc += dp2[N-1][suma/2]*3
print(allc%DIV)

### FIXED CODE ###

import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2),dtype = np.int)
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
	if(i%10 == 0):
		dp[i,:,:] = dp[i,:,:]%DIV
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))
### BUGGY CODE ###

n=int(input())
s=int(input())

No=0
for b in range(2,n+1):
    m=0
    N=n
    while N!=0:
        m+=N%b
        N=N//b
        if m>s:
            break
    if m==s:
        print(b)
        No=1
        break
if n==s:
    print(n+1)
    No =1
if No==0:
    print(-1)


### FIXED CODE ###

n=int(input())
s=int(input())

No=0
if n==s:
    print(n+1)
    No =1
else:
    for b in range(2,int(n**0.5)+2):
        m=0
        N=n
        while N!=0:
            m+=N%b
            N=N//b
            if m>s:
                break    
        if m==s:
            print(b)
            No=1
            exit()
    for p in range(int(n**0.5-1),0,-1):
        b = float(n-s)/float(p)+1.0
        if abs(b-int(b))<10**(-10)and b>0:
            b=int(b)
            m=0
            N=n
            while N!=0:
                m+=N%b
                N=N//b
                if m>s:
                    break    
            if m==s:
                print(b)
                No=1
                exit()
if No==0:
    print(-1)
### BUGGY CODE ###

import sys
from math import factorial

input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))

mod = 10**9 + 7

a.sort()

li = []
for i in range(n-1):
    li.append(a[i+1]-a[i])

ans = 0

dp = [1]
for i in range(1,n+1):
    dp.append(dp[-1]*i%mod)

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

comb1 = comb(n,k)

for i in range(n-1):
    if i+1 < k and n-i-1 < k:
        ans += li[i] * comb1
    elif i+1 < k:
        ans += li[i] * (comb1 - comb(n-i-1,k))
    elif n-i-1 < k:
        ans += li[i] * (comb1 - comb(i+1,k))
    else:
        ans += li[i] * (comb1 - comb(n-i-1,k) - comb(i+1,k))

print(ans%mod)


### FIXED CODE ###

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

mod = 10**9 + 7

a.sort(reverse = True)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(100010)
ans = 0

for i in range(n-k+1):
    ans += a[i] * comb(n-i-1, k-1)
    ans %= mod

a = a[::-1]

for i in range(n-k+1):
    ans -= a[i] * comb(n-i-1, k-1)
    ans %= mod

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

R,G,B,N = map( int, input().split())
count = 0
rmax = N//R
gmax = N//G
for r in range(rmax+1):
  tmp = r * R
  for g in range(gmax+1):
    tmp2 = tmp+g*G
    if N < tmp2:
      break
    if ((N - (tmp + g * G)) % B) == 0:
      count+=1
print(count)


### FIXED CODE ###

R,G,B,N = map( int, input().split())
count = 0
rmax = N//R
gmax = N//G
for r in range(rmax+1):
  tmp = r * R
  for g in range(gmax+1):
    tmp2 = N - (tmp+g*G)
    if tmp2 < 0:
      break
    if (tmp2 % B) == 0:
      count+=1
print(count)
### BUGGY CODE ###

from collections import Counter
N = int(input())
P = []
ans = 0
for _ in range(N):
    s = input()
    c = Counter(s)
    for p in P:
        if p == c:
            ans += 1
    P.append(c)
print(ans)



### FIXED CODE ###

from math import factorial
N = int(input())
P = {}
ans = 0
def counter(s):
    ret = [0]*26
    for ss in s:
        ret[ord(ss)-ord('a')] += 1
    return tuple(ret)
for _ in range(N):
    s = input()
    c = counter(s)
    if not c in P.keys():
        P[c] = 1
    else:
        P[c] += 1
for v in P.values():
    if v > 1:
        ans += factorial(v) // factorial(2) // factorial(v-2)
print(ans)
### BUGGY CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    if k[i] in d:
        d[k[i]] += 1
    else:
        d[k[i]] = 1
for key in d:
    dd[key] = d[key]*(d[key]-1)/2
for i in range(N):
    res = 0
    for key in d:
        if d[key]>1:
            if key == k[i]:
                res += (d[key]-1)*(d[key]-2)/2
            else:
                res += dd[key]
    print(int(res))

### FIXED CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    a = k[i]
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
tot = 0
for key in d:
    a = d[key]
    dd[key] = int(a*(a-1)/2)
    tot += dd[key]
for i in range(N):
    print(tot - d[k[i]]+1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def longest_path(s):
    global dp
    if adj[s]:
        dp[s-1]=max((longest_path(t)+1)for t in adj[s])
    else:
        dp[s-1]=0
    return dp[s-1]

N,M=map(int,input().split())
edge=[]
for _ in range(M):
    edge.append(list(map(int,input().split())))

adj={}
for n in range(1,N+1):
    l=[]
    for m in range(M):
        if edge[m][0]==n:
            l.append(edge[m][1])
    adj[n]=l

dp=[0]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))

### FIXED CODE ###

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

def longest_path(s):
    global dp
    if dp[s-1]<1:
        if edge[s]:
            dp[s-1]=max((longest_path(t)+1)for t in edge[s])
        else:
            dp[s-1]=0
    return dp[s-1]

N,M=map(int,input().split())
edge={}
for i in range(1,N+1):
    edge.setdefault(i,[])
for _ in range(M):
    x,y=map(int,input().split())
    edge[x].append(y)
dp=[0]*N
for i in range(1,N+1):
    if dp[i-1]==0:
        longest_path(i)

print(max(dp))
### BUGGY CODE ###

N=int(input())
S=input()
R=[]
G=[]
B=[]

for n in range(N):
  if S[n]=="R":
    R.append(n)
  elif S[n]=="G":
    G.append(n)
  else:
    B.append(n)

ans=len(R)*len(G)*len(B)

for r in R:
  for g in G:
    for b in B:
      list=[r,g,b]
      list.sort()
      if list[2]-list[1]==list[1]-list[0]:
        ans -=1

print(ans)
      
    
    

### FIXED CODE ###

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

ans=S.count("R")*S.count("G")*S.count("B")

#j-i= k-j k=2*j-i

for i in range(N):
  for j in range(i+1,N):
    if 2*j-i<N:
      if S[i]!=S[j] and S[i]!=S[2*j-i] and S[j]!=S[2*j-i]:
        ans -=1
        
print(ans)