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

import collections, sys
sys.setrecursionlimit(10**5 + 5)
N, *A = [int(_) for _ in open(0).read().split()]
win_lose = {i: set() for i in range(1, N + 1)}
for win, lose in zip(A, range(2, N + 1)):
    win_lose[win].add(lose)

memo = [-1] * (N + 1)


def rec(x):
    if memo[x] == -1:
        if win_lose[x] == set():
            memo[x] = 0
        else:
            memo[x] = max(a + b for a, b in zip(
                sorted(rec(y) for y in win_lose[x])[::-1], range(1, N + 1)))
    return memo[x]


print(rec(1))


### FIXED CODE ###

import collections
N, *A = [int(_) for _ in open(0).read().split()]
win_lose = {i: set() for i in range(1, N + 1)}
for win, lose in zip(A, range(2, N + 1)):
    win_lose[win].add(lose)

s1 = [1]
s2 = []
while s1:
    a = s1.pop()
    s2 += [a]
    for b in win_lose[a]:
        s1 += [b]
memo = [0] * (N + 1)
for x in s2[::-1]:
    if win_lose[x] == set():
        memo[x] = 0
    else:
        memo[x] = max(a + b for a, b in zip(
            sorted(memo[y] for y in win_lose[x])[::-1], range(1, N + 1)))
print(memo[1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

#%%
def dfs(gr,li,pt,n,fr):
    li[n] += pt
    if(len(gr[n])==1 and gr[n][0]==fr):
        return True
    else:
        for i in gr[n]:
            if(i==fr):continue
            dfs(gr,li,li[n],i,n)
        return True
#%%
N,Q = [int(x) for x in input().split()]
li = [0]*N
gp = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = [int(x) for x in input().split()]
    gp[a-1].append(b-1)
    gp[b-1].append(a-1)

for _ in range(Q):
    p,x = [int(x) for x in input().split()]
    li[p-1] += x

dfs(gp,li,0,0,-1)
print(*li)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,Q = [int(x) for x in input().split()]
    li = [0]*N
    gp = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = input().split()
        a = int(a)
        b = int(b)
        gp[a-1].append(b-1)
        gp[b-1].append(a-1)

    for _ in range(Q):
        p,x = input().split()
        li[int(p)-1] += int(x)

    st = []
    seen = set()
    st.append(0)
    while(st):
        x = st.pop()
        if(x in seen):continue
        seen.add(x)
        for i in gp[x]:
            if(i in seen):continue
            li[i]+=li[x]
            st.append(i)
    print(*li)

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

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-x//F,0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)

### FIXED CODE ###

n,k=map(int,input().split())
a=[int(i) for i in input().split()]
f=[int(i) for i in input().split()]

# aとfの組み合わせはソートして逆向きが最適
# 帰納法で示す

# チームの成績x→単に成績x,メンバーiの成績→xi

# 0<=x<=a[-1]*f[0]な整数xがあったら
# 成績x以下にすることはできるか？という命題を考える

# gi=int(x/fi)は食べ物iで成績xiを出せる最大値
# 　aiがgiを超えてしまうと成績xi以下は修行しないと出せない
# 　ai<=giならその人の成績はxi以下になる
# なのでmax(ai-gi,0)は成績xi以下であるために必要な修行の回数

# よってsum=Σmax(ai-gi,0)は成績x以下を達成するのに、必要なチーム全体の総修行回数
# したってsum<=Kなら成績x以下にすることができる

# 各整数について命題はFalseかTrueを返す
# その順番は1から順にF...FT...Tとなる
# この一番左のTの整数xが求めたい最小値：チームの成績xの最小値

a.sort()
f.sort(reverse=True)

def score(x):
    syugyo = 0
    for A,F in zip(a,f):
        syugyo += max(A-int(x/F),0)
    if syugyo <= k:
        return True
    else:
        return False


left = 0
right = a[-1]*f[0]+1
while left < right-1:
    mid = (left+right)//2
    if score(mid):
        right = mid
    else:
        left = mid
print(left+1 if left != 0 else 0)
    
# 計算量は 1+2logN + N*log(2)N <= N*logN < 3.6 * 10^6 
# ぎりぎりセーフ？
### BUGGY CODE ###

import sys
n = int(input()) 
a = list(map(int,input().split()))
c = 1

for i in range(n):
    c *= a[i]

if (c > (10**18)):
    print("-1")
    sys.exit()
else:
    print(c)





### FIXED CODE ###

import sys
n = int(input()) 
a = list(map(int,input().split()))
c = 1

for i in range(n):
    if(a[i] == 0):
        print("0")
        sys.exit()
else:        
    for i in range(n):
        c *= a[i]
        if (c > (10**18)):
            print("-1")
            sys.exit()

print(c)
### BUGGY CODE ###

n,m,k = map(int, input().split())
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 = 998244353
N = n  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
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)

ans = 0
for i in range(k+1):
  a = m*(m-1)**(n-i-1)%p
  a *= cmb(n-1, i, p)%p
  ans += a
print(ans%p)

### FIXED CODE ###

n,m,k = map(int, input().split())
#ncr
mod = 998244353
class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod 
    def ncr(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod 
cmb = Combination(n)
ans = 0
for i in range(k+1):
  a = m*pow(m-1,n-i-1,mod)%mod
  a *= cmb.ncr(n-1,i)
  ans += a%mod
print(ans%mod)
### BUGGY CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = []
for i, j in combinations(range(1, N+1), 2):
    mins = min([j-i, abs(Y-j)+abs(X-i)+1])
    result.append(mins)
print(N)
for i in range(1, N-1):
    print(result.count(i+1))

### FIXED CODE ###

from itertools import combinations
N, X, Y = map(int, input().split())

result = [0]*N
for i, j in combinations(range(1, N+1), 2):
    mins = min([j-i, abs(Y-j)+abs(X-i)+1])
    result[mins] += 1
    
for i in range(1, N):
    print(result[i])
### BUGGY CODE ###

# B - Frog 2
N, K = map(int,input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*N

dp[0] = 0
for i in range(1,N):
    if i == 1:
        dp[1] = abs(h[1]-h[0])
    else:
        for k in range(1,K+1):
            dp1 = dp[i - k]+ abs(h[i] - h[i - k])
            if dp[i] >= dp1:
                dp[i] = dp1
            else:
                pass

print(dp[N-1])

### FIXED CODE ###

#B - Frog 2
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 9] * N
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2,N):
    for j in range(K,0,-1):
        dp[i] = min(dp[i],dp[i-j] + abs(h[i] - h[i-j]))

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

X,K,D = map(int,input().split()) 
mlist = []
for i in range(K+1):
    t = X + i*D - (K-i)*D
    if t < 0 :
        t = -t
    mlist.append(t)
print(min(mlist))

### FIXED CODE ###

X,K,D = map(int,input().split()) 
X = abs(X)
if X >= K*D:
    print(X-K*D)
else:
    if (K-X//D) % 2 == 1:
        print(D-(X-X//D*D))
    else:
        print(X-X//D*D)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
# dp[i][j]:i<=j,i番目からj番目までの数列(j-i+1個)を前にした時、ゲーム終了までに自分が取れる最大得点。i,j=0,..,n-1
sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
print(2*dp[0][-1]-sa[-1])


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
# dp[i][j]:i<=j,i番目からj番目までの数列(j-i+1個)を前にした時、ゲーム終了までに自分が取れる最大得点。i,j=0,..,n-1
sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
print(2*dp[0][-1]-sa[-1])
### BUGGY CODE ###

STRI = input()
DICT = STRI.split()
A=int(DICT[0])
B=int(DICT[1])
K=int(DICT[2])
cA=A
cB=B
stop = False

for TIMES in range(K):
    if cA > 0:
        cA=cA-1
    elif cB > 0:
        cB=cB-1
    else:
        stop = True

print(str(cA) + " " + str(cB))

### FIXED CODE ###

STRI = input()
DICT = STRI.split()
A=int(DICT[0])
B=int(DICT[1])
K=int(DICT[2])

cA = A
cB = B

if A+B <= K:
    cA = 0
    cB = 0
else:
    if A >= K:
        if A == K:
            cA = 0
        elif A > K:
            cA = A - K
    else:
        cA = 0
        if A+B <= K:
            cA = 0
            cB = 0
        else:
            cB = B - (K - A)

print(cA,cB)
### BUGGY CODE ###

K=int(input())
a=7
count=1
for i in range(K):
    if a%K==0:
        print(count)
        break
    a=a*10+7
    count+=1
if count==K+1:
    print(-1)


### FIXED CODE ###

K=int(input())
a=7
count=1
for i in range(K):
    if a%K==0:
        print(count)
        break
    a=(a*10+7)%K
    count+=1
if count==K+1:
    print(-1)
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y
def primes(n):
    P = [2]
    for L in range(3, n):
        isP = True
        for L2 in P:
            isP = isP and L%L2
            if not isP: break
        if isP: P.append(L)
    return P


N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP={}
for _ in range(M):
    i, j = LI()
    if not i in MP: MP[i] = []
    MP[i].append(j)
# print(MP)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

len_1 = len(MP[1])

# print("len_1: {}".format(len_1))
# print(RES)


result = 10.0**15
RESN = [0]*(N+1)
for i in range(1, N-1):
    skip = False
    for k in range(N+1): RESN[k] = -1
    RESN[N] = 0

    max_j, max_value = 0, 0

    for j in MP[i]:
        if RES[j] > max_value:
            max_value = RES[j]
            max_j = j

    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        if div == 0:
            skip = True
            break
        else:
            RESN[k] = next_E / div
    if not skip:
        result = min(result, RESN[1])

print(min(result, RES[1]))


### FIXED CODE ###

def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()
### BUGGY CODE ###

import math


n = int(input())


c = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            temp = math.gcd(i+1,j+1)
            c += math.gcd(temp,k+1)

print(c)

### FIXED CODE ###

import math
# from functools import reduce
# from fractions import gcd
def main():
    n = int(input())
    # def gcd(*numbers):
    #     return reduce(math.gcd, numbers)

    c = 0
    for i in range(n):
        for j in range(n):
            for k in range(n):
                temp = math.gcd(i+1,j+1)
                c += math.gcd(temp,k+1)

    print(c)

main()
### BUGGY CODE ###

n = int(input())
m = 0
a = list(map(int,input().split()))
b = []
for i in range(n,0,-1):
  if n // i >= 2:
# i の倍数の箱のボールの数とa[i] でXORをとってあげる。
    if ((sum([a[j-1] for j in a if j%i == 0]))%2)%2:
      b.append(i)
  else:
    if a[i-1] == 1:
      b.append(i)
print(len(b))
#print(b)
if len(b) != 0:
  print(*b)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
m = 0
res = []
# 1 idx
for i in range(n, 0, -1):
    # i の倍数でbit立っているものの個数を数える
    cnt = 0
    idx = 2
    while i * idx <= n:
        if ans[i * idx - 1]:
            cnt += 1
        idx += 1
    debug = cnt
    if cnt % 2 != a[i - 1]:
        ans[i - 1] = 1
        m += 1
        res.append(i)
print(m)
if m:
    print(*res)
### BUGGY CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


N = int(input())
X = bin(int(input(), 2))
# print(f'X = {X}')


def count_bit(n):
    bin_num = bin(n)[2:]
    count = 0
    for i in bin_num:
        count += int(i)
    return count


def popcount(n):
    if n == 0:
        memo_p[0] = 0
        return 0
    if n == 1:
        memo_p[1] = 1
        return 1
    if n in memo_p.keys():
        return memo_p[n]
    memo_p[n] = count_bit(n)
    return memo_p[n]


def f(n):
    # print(f'called f[{n}]')
    if n == 0:
        memo_f[0] = 0
        return 0
    if n == 1:
        memo_f[1] = 1
        return 1
    if n == 2:
        memo_f[2] = 1
        return 1
    if n in memo_f.keys():
        return memo_f[n]
    # print(f'{n} is not found')
    r = n % popcount(n)
    # print(f'popcount = {popcount(n)}')
    # print(f'r = {r}')
    memo_f[n] = f(r) + 1
    return memo_f[n]


memo_p = {}
memo_f = {}

for i in range(N):
    # print(f'i = {i}')
    num = None
    if int(X, 2) & (1 << (N-1-i)):
        num = int(X, 2) - 2 ** (N-1-i)
    else:
        num = int(X, 2) + 2 ** (N-1-i)
    # print(f'num = {num}')
    print(f(num))


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


n = int(input())
x = input()
x_pc = x.count('1')
x_pc_plus = x_pc + 1
x_pc_minus = x_pc - 1

# 2 ** i % x_pc_plus, 2 ** i % x_pc_minus を予め計算しておく
r_plus_list = [pow(2, i, x_pc_plus) for i in range(n+1)]
r_minus_list = [0] * (n+1)
if x_pc_minus > 0:
    r_minus_list = [pow(2, i, x_pc_minus) for i in range(n+1)]

x = x[::-1]
r_plus = 0
r_minus = 0
for i in range(n):
    if x[i] == '1':
        r_plus += r_plus_list[i]
        r_minus += r_minus_list[i]

for i in range(n-1, -1, -1):
    if x[i] == '0':
        diff = (r_plus + r_plus_list[i]) % x_pc_plus
    elif x_pc_minus >= 1:
        diff = (r_minus - r_minus_list[i]) % x_pc_minus
    else:
        print(0)
        continue
    ans = 1
    while diff > 0:
        diff = diff % bin(diff).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
l = [list(input()) for i in range(h)]

dis = [[10000]*w for i in range(h)]
q = deque([])

for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            q.append([i,j,0])
            dis[i][j] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
while q:
    x,y,d = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and dis[nx][ny] > d+1:
            dis[nx][ny] = d + 1
            q.append([nx,ny,d+1])

ans = 0
for i in dis:
    ans = max(ans,max(i))
print(ans)


### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
l = [list(input()) for i in range(h)]

dis = [[10000]*w for i in range(h)]
q = deque([])

for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            q.append([i,j,0])
            dis[i][j] = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
while q:
    x,y,d = q.popleft()

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w and dis[nx][ny] > d+1:
            dis[nx][ny] = d + 1
            q.append([nx,ny,d+1])

ans = 0
for i in dis:
    ans = max(ans,max(i))
print(ans)
### BUGGY CODE ###

a=int(input())
b=list(map(int,input().split()))
ans=0
for i in range(1,a+1):
    print(b.count(i))

### FIXED CODE ###

a=int(input())
b=[0]*a
c=list(map(int,input().split()))
for i in c:
    b[i-1]+=1
print(*b,sep="\n")
### BUGGY CODE ###

n = int(input())
item = []
for i in range(n):
  s = input()
  if(s not in item):
    item.append(s)
print(len(item))

### FIXED CODE ###

n = int(input())
item = set()
for i in range(n):
  s = input()
  item.add(s)
print(len(item))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]

    def factorization(n):
        ret = set()
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                ret.add(i)

        if temp != 1:
            ret.add(temp)

        if len(ret) == 0 and n != 1:
            ret.add(n)

        return ret

    s = factorization(g)
    ls = len(s)
    flag = True
    for x in A[1:]:
        g = gcd(g, x)
        tmp = factorization(x)
        l = len(tmp)
        s |= tmp
        if len(s) != ls + l:
            flag = False
        ls = len(s)

    if flag:
        print("pairwise coprime")
    elif g == 1:
        print("setwise coprime")

    else:
        print("not coprime")


main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    from math import gcd
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    M = max(A)
    X = [i for i in range(M+1)]
    S = [True for i in range(M+1)]
    S[0] = False
    S[1] = False

    for i in range(1, M+1):
        if S[i]:
            for j in range(i, M+1, i):
                if S[j]:
                    S[j] = False
                    X[j] = i
    flag = True
    s = set()
    ls = 0
    for x in A:
        tmp = set()
        while(X[x] != 1):
            tmp.add(X[x])
            x //= X[x]
        l = len(tmp)
        s |= tmp
        if len(s) == ls + l:
            ls += l
            continue
        else:
            flag = False
            break

    if flag:
        print("pairwise coprime")
    else:
        for x in A[1:]:
            g = gcd(g, x)
        if g == 1:
            print("setwise coprime")

        else:
            print("not coprime")


main()
### BUGGY CODE ###

import numpy as np

n = int(input())

dams = list(map(int, input().split()))
dams = np.array(dams, dtype = np.int)

ans_list = []

kake = [1*(-1)**x for x in range(n)]
ans_list = [0 for x in range(n)]
kake_temp = kake
out = ""
for i in range(n):
  #print(kake_temp)
  ans = int(np.dot(dams, np.array(kake_temp)))
  out += str(ans) + " " 
  kake_temp = [kake_temp[-1]] + kake_temp[0 : n - 1]
  
print(out[:-1])
  

### FIXED CODE ###

n = int(input())

dams = list(map(int, input().split()))
ans_list = [0 for x in range(n)]

ans_list[0] = sum([dams[x]*(-1)**x for x in range(n)])

for i in range(1, n):
  ans_list[i] = -ans_list[i-1] + 2 * dams[i - 1]

print(" ".join(list(map(str, ans_list))))

#print(*ans_list)
### BUGGY CODE ###

from itertools import combinations
MOD = 10**9 + 7
n=int(input())
a=list(map(int,input().split()))
sum=0
for x,y in combinations(a,2):
   sum+=x*y%MOD
   ans=sum%MOD
print(ans)

### FIXED CODE ###

mod = 10**9 + 7
n=int(input())
s=list(map(int,input().split()))
s2=sum(map(lambda x: x ** 2,s))
ans=(((sum(s))**2)-(s2))//2%mod
print(ans)
### BUGGY CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')
sum_rgb = r*g*b

# rgbの組み合わせの総数から距離が等しいものを引く
for i in range(N-2):
    for j in range(i+1, N-1):
        k = j + (j-i)
        if k > N-1:
            continue
        if len(set([S[i], S[j], S[k]])) == 3:
            sum_rgb -= 1
print(sum_rgb)

### FIXED CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')
sum_rgb = r*g*b

# rgbの組み合わせの総数から距離が等しいものを引く
for i in range(N-2):
    for j in range(i+1, N-1):
        k = j + (j-i)
        if k > N-1:
            continue
        if len(set([S[i], S[j], S[k]])) == 3:
            sum_rgb -= 1
print(sum_rgb)
### BUGGY CODE ###

n = int(input())
S = input()

def c(s1, s2, s3, i, s):
  cnt = 0
  L = S[:i]
  R = S[i+1:]
  # print(s1, s2, s3, L, R)
  if s == s1:
    lc = 0
    for l in L:
      if l == s2:
        lc += 1
    rc = 0
    for r in R:
      if r == s3:
        rc += 1
    cnt += lc * rc 
  for i, j in zip(R, L[::-1]):
    if s1 == s and i == s3 and j == s2:
      cnt -= 1
  # print(cnt)
  return cnt

ans = 0
for i, s in enumerate(S):
  ans += c("R", "B", "G", i, s) 
  ans += c("R", "G", "B", i, s) 
  ans += c("B", "R", "G", i, s) 
  ans += c("B", "G", "R", i, s) 
  ans += c("G", "R", "B", i, s) 
  ans += c("G", "B", "R", i, s) 

print(ans)

### FIXED CODE ###

n = int(input())
S = input()

def c(s1, s2, s3, i, s):
  cnt = 0
  L = S[:i]
  R = S[i+1:]
  # print(s1, s2, s3, L, R)
  if s == s1:
    lc = 0
    for l in L:
      if l == s2:
        lc += 1
    rc = 0
    for r in R:
      if r == s3:
        rc += 1
    cnt += lc * rc 
  for i, j in zip(R, L[::-1]):
    if s1 == s and i == s3 and j == s2:
      cnt -= 1
  # print(cnt)
  return cnt

ans = 0
for i, s in enumerate(S):
  ans += c("R", "B", "G", i, s) 
  ans += c("R", "G", "B", i, s) 
  ans += c("B", "R", "G", i, s) 
  ans += c("B", "G", "R", i, s) 
  ans += c("G", "R", "B", i, s) 
  ans += c("G", "B", "R", i, s) 

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

#!/usr/local/env python3

import sys
from itertools import combinations


def find_all_subsets_of_target_sum(numbers, target_sum):
    subsets = []
    for x in range(len(numbers)):
        subsets.extend([
                combo for combo in combinations(numbers, x)
                if sum(combo) == target_sum
            ]
        )
    return subsets


def find_num_of_subset_with_x_elements(upper_bound, target_sum, x_elements):
    numbers = [int(number) for number in range(1, upper_bound+1)]
    subsets = find_all_subsets_of_target_sum(numbers, target_sum)
    subset_count = 0
    for subset in subsets:
        if len(subset) == x_elements:
            subset_count += 1
    return subset_count


def program_runner():
    while True:
        n, x = map(int, sys.stdin.readline().split())
        if n == x == 0:
            break
        print(find_num_of_subset_with_x_elements(n, x, 3))


def main():
    program_runner()


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/local/env python3

import sys


def main():
    while True:
        count = 0
        n, r = map(int, sys.stdin.readline().split())
        if n == r == 0:
            break
        for n1 in range(1, n-1):
            for n2 in range(n1+1, n):
                for n3 in range(n2+1, n+1):
                    if n1 + n2 + n3 == r:
                        count += 1
        print(count)


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

import numpy as np

def intinput():
    return map(int,input().split())

n,m=intinput()
x=np.arange(1,n+1)
z=np.ones(n,bool)
for i in range(m):
    a,b=intinput()
    y = np.logical_and(a<=x,x<=b)
    z = np.logical_and(y,z)
print(np.sum(z))

### FIXED CODE ###

import sys

def intinput():
    return map(int,sys.stdin.readline().split())

n,m=intinput()
a1=0
b1=n+1
for i in range(m):
    a,b=intinput()
    a1 = max(a,a1)
    b1 = min(b,b1)
if b1>=a1:
    print(b1-a1+1)
else:
    print(0)