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

from itertools import combinations
n=int(input())
li=[int(x) for x in input().split()]
l = list(range(n))
s = combinations(l,3)

d=0
for a,b,c in list(s):
    if li[a]<(li[b]+li[c]):
        if li[b]<(li[a]+li[c]):
            if li[c]<(li[b]+li[a]):
                d=d+1
print(d)

### FIXED CODE ###


def findnumberofTriangles(arr): 
	n = len(arr) 
	arr.sort() 
	count = 0
	for i in range(0, n-2):  
		k = i + 2 
		for j in range(i + 1, n):  
			while (k < n and arr[i] + arr[j] > arr[k]): 
				k += 1
			if(k>j): 
				count += k - j - 1

	return count 

n = int(input())
arr=[int(x) for x in input().split()]
print(findnumberofTriangles(arr))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    FF = []
    for i in range(n):
        if A[A[i] - 1] == i + 1 and A[i] not in set(FF):
            res += 1
            FF.append(A[A[i] - 1])
            FF.append(i + 1)

    print(res)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for i in range(n):
        if A[A[i] - 1] == i + 1:
            res += 1

    print(res // 2)


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

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

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0
for i in range(1, N + 1):
    for k in range(1, K + 1):
        if i + k <= N:
            if dp[i] + abs(h_list[i - 1] - h_list[i - 1 + k]) < dp[i + k]:
                dp[i + k] = dp[i] + abs(h_list[i - 1] - h_list[i - 1 + k])

print(dp[N])


### FIXED CODE ###

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

dp = [float("inf") for _ in range(N + 1)]
dp[1] = 0
for i in range(1, N+1):
    for k in range(1, K+1):
        if i + k <= N:
            dp[i+k] = min(dp[i + k], dp[i] + abs(h_list[i-1] - h_list[i-1+k]))

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

def resolve():
    s = str(input())
    ans = 0
    while True:
        origin = s
        cnt = s.count('BW')
        s = s.replace('BW', 'WB')
        if origin == s:
            break
        ans += cnt
    print(ans)

    return
resolve()

### FIXED CODE ###

def resolve():
    s = str(input())
    ans = 0
    ind = []
    for i, char in enumerate(s):
        if char == 'W':
            ind.append(i)
    lst = 0
    # print(ind)
    for i in ind:
        ans += (i - lst)
        lst += 1

    # idx = s.index('W')
    print(ans)
    return


resolve()
### BUGGY CODE ###

class BIT_index:
    def __init__(self, n):
        self.BIT_prev = [n] * (n + 1)
        self.BIT_next = [n] * (n + 1)
        self.n = n

    def __addElement(self, BIT, idx):
        value = idx
        idx += 1
        while idx > 0:
            BIT[idx] = min(BIT[idx], value)
            idx -= idx & -idx

    def addElement(self, idx):
        self.__addElement(self.BIT_prev, self.n - 1 - idx)
        self.__addElement(self.BIT_next, idx)

    def __getIndex(self, BIT, idx):
        idx += 1
        ans = self.n
        while idx <= self.n:
            ans = min(ans, BIT[idx])
            idx += idx & -idx
        return ans

    def getIndexPrev(self, idx):
        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)

    def getIndexNext(self, idx):
        return self.__getIndex(self.BIT_next, idx)


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

Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]

BIT = BIT_index(N)
ans = 0
for i, B in enumerate(Bs):
    iN = BIT.getIndexNext(B)
    iP = BIT.getIndexPrev(B)
    BIT.addElement(B)
    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))

print(ans)



### FIXED CODE ###

class BIT_index:
    def __init__(self, n):
        self.BIT_prev = [n] * (n + 1)
        self.BIT_next = [n] * (n + 1)
        self.n = n

    def __addElement(self, BIT, idx):
        value = idx
        idx += 1
        while idx > 0:
            BIT[idx] = min(BIT[idx], value)
            idx -= idx & -idx

    def addElement(self, idx):
        self.__addElement(self.BIT_prev, self.n - 1 - idx)
        self.__addElement(self.BIT_next, idx)

    def __getIndex(self, BIT, idx):
        idx += 1
        ans = self.n
        while idx <= self.n:
            ans = min(ans, BIT[idx])
            idx += idx & -idx
        return ans

    def getIndexPrev(self, idx):
        return self.__getIndex(self.BIT_prev, self.n - 1 - idx)

    def getIndexNext(self, idx):
        return self.__getIndex(self.BIT_next, idx)


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

Bs = [i for A, i in sorted([(As[i], i) for i in range(N)])]

BIT = BIT_index(N)
ans = 0
for i, B in enumerate(Bs):
    iN = BIT.getIndexNext(B)
    iP = BIT.getIndexPrev(B)
    BIT.addElement(B)
    ans += (i + 1) * (iN - B) * (B - (N - 1 - iP))

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

N,K = [int(e) for e in input().split()]
asiba = [int(e) for e in input().split()]
dp =[0] *N

#初期化
dp[0]=0
dp[1]=abs(asiba[1]-asiba[0])

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

### FIXED CODE ###

def main():
  n, k = [int(e) for e in input().split()]
  h = [int(e) for e in input().split()]
  cost = [0] * n
  for i in range(1, n):
    cost[i] = min(abs(h[i] - h[j]) + cost[j] for j in range(max(0, i - k), i))
  print(cost[n - 1])
main()
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
sum = 0
for i in range(min(a, k)):
    sum += 1
for i in range(min(k-a-b, c)):
    sum += -1
print(sum)

### FIXED CODE ###

a, b, c, k = map(int, input().split())
sum = k
if k > a:
    sum = a
    if k-a <= b:
        sum = a
    else:
        sum = 2*a+b-k
print(sum)
### BUGGY CODE ###

ss = list(input())
s = []
for i in ss:
  if i == 'A':
    s.append(1)
  elif i == 'B':
    s.append(2)
  else:
    s.append(3)
n = len(s)
ans = 0
while True:
    b = False
    for i in range(0, n-2):
        if s[i:i+3] == [1, 2, 3]:
            s[i] = 2
            s[i+1] = 3
            s[i+2] = 1
            ans += 1
            b = True
    if not b:
        break
print(ans)


### FIXED CODE ###

s = list(input())
li = []
n = len(s)
ans = 0
b = False
for i in range(n-1):
    if b:
        b = False
        continue
    if s[i] + s[i+1] == 'BC':
        li.append('D')
        b = True
    if s[i] == 'B' and s[i+1] != 'C':
        li.append('E')
    if s[i] == 'C':
        li.append('E')
    if s[i] == 'A':
        li.append('A')
cnt = 0
for i in range(len(li)):
    if li[i] == 'A':
        cnt += 1
    elif li[i] == 'E':
        cnt = 0
    else:
        ans += cnt
print(ans)
### BUGGY CODE ###

X = input()
X = list(X)
prev = ""
for i in range(len(X) - 1):
    if X[i] + X[i + 1] == "ST":
        a = X.pop(i + 1)
        b = X.pop(i)
        c = [b,a]
        X = c + X

for i in range(0, len(X)):
    if X[len(X) - (i+1)] == "T":
        print(i * 2)
        break


### FIXED CODE ###

X = input()
Y = []
for i in X:
    Y.append(i)
    if len(Y) > 1:
        if Y[-2] + Y[-1] == "ST":
            Y.pop()
            Y.pop()
print(len(Y))
### BUGGY CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())
 
 
li.sort(reverse=True,key=lambda x:x[1])
 

def calc_score(li,choice):
    score=0
    k=[]
    for i in choice:
        score+=li[i][1]
        k.append(li[i][0])        
    score+=len(set(k))**2
    return score

def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))

first_choice=list(range(k))
score=calc_score(li,first_choice)

li_choice_set=set([li[i][0] for i in first_choice])


s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(first_choice,li)

for i in range(s1+1,s2+1):
  
    new_choice=first_choice.copy()
    change=i-s1
    can_append=change
    must_delete=change
    

    
    
    for j in range(k,n):
     #   print(set([li[i][0] for i in new_choice]),i,li[j][0])
        if li[j][0] not in [li[i][0] for i in new_choice]:
            
            new_choice.append(j)
            can_append+=-1
            if can_append==0:
                break
            
            
    for j in range(k-1,-1,-1):

        if li[j][0] in [li[p][0] for p in range(j)]:
            new_choice.remove(j)
            must_delete+=-1
            if must_delete==0:
                break
        
    
    new_score=calc_score(li,new_choice)

    
    if score<new_score:
        score=new_score
        
    
print(score)

### FIXED CODE ###

n,k=map(int,input().split())
li=[[0,0] for i in range(n)]
for i in range(n):
    li[i][0],li[i][1]=map(int,input().split())



def find_num_neta(choice,li):
    k=[]
    for i in choice:
        k.append(li[i][0])
    return len(set(k))
#-----------------------------------------

li.sort(reverse=True,key=lambda x:x[1])
s2=min(find_num_neta(list(range(n)),li),k)
s1=find_num_neta(list(range(k)),li)
oishisa=sum([li[i][1] for i in range(k)])
score=oishisa+s1**2

#-----------------------------------------
li.sort(key=lambda x:x[0])
best_list=[]
not_best_list=[]


m=-1
for i in li:
    if m==i[0]:
        not_best_list.append(i)
    else:
        best_list.append(i)
        m=i[0]
        
not_best_list.sort(reverse=True,key=lambda x:x[1])
best_list.sort(reverse=True,key=lambda x:x[1])



 
 
for i in range(s1+1,s2+1):
    oishisa=oishisa+best_list[i-1][1]-not_best_list[k-i][1]
    
    new_score=i**2+oishisa
    
    if score<new_score:
        score=new_score
        
    
print(score)
### BUGGY CODE ###

mod = 10**9+7
n,a,b = map(int, input().split())
ans = 0
c = 1
x = n
if a!=n and b!=n: ans+=c
for i in range(1,(n+2)//2):
    c = c*x//(n+1-x)
    x-=1
    ans += c*2
    if i==a or n-i==a:
        ans -= c
    if i==b or n-i==b:
        ans -= c
    if i==n/2:
        ans -= c

print(ans%mod)

### FIXED CODE ###

n,a,b = map(int, input().split())

mod = 10**9+7
ans = pow(2,n,mod)-1

nca = 1
ncb = 1

for i in range(b):
    ncb = ncb*(n-i)%mod
    ncb *= pow(i+1,mod-2,mod)
    if i+1==a:
        nca = ncb

ans -= nca+ncb
print(ans%mod)
### BUGGY CODE ###

n,p = map(int,input().split())
s = input()
ans = 0
for i in range(n):
    for j in range(i+1,n+1):
        tar = int(s[i:j])
        if tar%p == 0: ans += 1

print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:
    for i,c in enumerate(s,1):
        if int(c)%p == 0: ans += i
else:
    cnt = [0]*p
    cnt[0] = 1
    x = 0
    d = 1
    for c in s[::-1]:
        x += d*int(c)
        x %= p
        cnt[x%p] += 1
        d *= 10
        d %= p
    # print(cnt)
    for v in cnt: ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

[K, S] = map(int, input().split())
ret = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if (x + y + z) == S:
                ret += 1
print(ret)


### FIXED CODE ###

[K, S] = map(int, input().split())
ret = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if 0 <= z and z <= K:
            ret += 1
print(ret)
### BUGGY CODE ###

from math import ceil
from bisect import bisect_left


def solve(n, h):
    a = []
    b = []

    for i in range(n):
        ai, bi = map(int, input().split())
        a.append(ai)
        b.append(bi)
        a.sort()
        b.sort()

    if n == 1:
        ans = ceil((h-b[n-1])/a[n-1])+1

    else:
        over_amax = b[bisect_left(b, a[n-1]):]
        if h <= sum(over_amax):
            ans = len(over_amax)
        else:
            ans = ceil((h - sum(over_amax)) / a[n-1]) + len(over_amax)

    return ans


if __name__ == '__main__':
    n, h = map(int, input().split())
    print(solve(n, h))


### FIXED CODE ###

from math import ceil
from bisect import bisect_left


def solve(n, h):
    a = []
    b = []

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

    amax = max(a)
    b.sort()

    if n == 1:
        ans = ceil((h-b[n-1])/amax)+1

    else:
        over_amax = b[bisect_left(b, amax):]
        if h <= sum(over_amax):
            for j in range(n-1, -1, -1):
                h -= b[j]
                if h <= 0:
                    ans = n-j
                    break

        else:
            ans = ceil((h - sum(over_amax)) / amax) + len(over_amax)

    return ans


if __name__ == '__main__':
    n, h = map(int, input().split())
    print(solve(n, h))
### BUGGY CODE ###

S=input()
T=input()

i=0
L=len(S)
while i<L:
    if S[i]!=T[i]:
        S=S.translate(str.maketrans({S[i]: T[i], T[i]: S[i]}))
    i+=1

if S==T:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S=input()
T=input()
L=len(S)

LISTS=[[] for i in range(30)]
LISTT=[[] for i in range(30)]

for i in range(L):
    LISTS[ord(S[i])-97].append(i)
    LISTT[ord(T[i])-97].append(i)


check=1
for i in range(30):
    if len(LISTS[i])>=2:
        for j in range(1,len(LISTS[i])):
            if T[LISTS[i][j]]!=T[LISTS[i][j-1]]:
                check=0


    if len(LISTT[i])>=2:
        for j in range(1,len(LISTT[i])):
            if S[LISTT[i][j]]!=S[LISTT[i][j-1]]:
                check=0

if check==1:
    print("Yes")

else:
    print("No")
### BUGGY CODE ###

from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

for a in A:
    lcm = (lcm * a) // gcd(lcm, a)

ans = 0
for a in A:
    ans += lcm // a
    ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

for a in A:
    lcm = (lcm * a) // gcd(lcm, a)

ans = 0
for a in A:
    ans += (lcm % MOD) * pow(a, MOD - 2, MOD)
    ans %= MOD

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

N = int(input())
b = [int(x) for x in input().split()]
li=[]
def dfs(B,li):
    if(B == []):
        return True
    if(max(B)>len(B)):
        return False
    for index,i in enumerate(B):
        if(index == i-1):
            if(index == 0):
                if(dfs(B[1:],li)):
                    li.append(i)
                    return True
            else:
                if(dfs(B[:index]+B[index+1:],li)):
                    li.append(i)
                    return True
    return False

if(dfs(b,li)):
    for i in li:
        print(i)
else:
    print(-1)

### FIXED CODE ###

N = int(input())
b = [int(x) for x in input().split()]
li=[]
def dfs(B,li):
    cand = []
    if(B == []):
        return True
    if(max(B)>len(B)):
        return False
    for i in range(1,len(B)+1):
        if(i in B):
            if(B.index(i)+1<i):
                return False
            elif(B.index(i)+1==i):
                cand.append(i)

    for i in cand:
        if(dfs(B[:i-1]+B[i:],li)):
            li.append(i)
            return True

    return False

if(dfs(b,li)):
    for i in li:
        print(i)
else:
    print(-1)
### BUGGY CODE ###

k, s = map(int, input().split())
if s < k:
    k = s

count = 0
for x in range(k+1):
    for y in range(k+1):
        if x+y > s:
            break
        for z in range(k+1):
            if x+y+z == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z < 0:
            break
        if z <= k:
            count += 1

print(count)
### BUGGY CODE ###

import copy

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n) for n in input().split() ] )

empty = [ [] for i in range(N) ]
default = [0 for i in range(N)]
day = 0
while(True):
    day += 1
    v = copy.deepcopy(default)
    for p in range(N):
        if len(A[p]) == 0:
            continue
        q = A[p][0]-1
        if v[p] == 0  and  v[q] == 0  and  A[q][0]-1 == p:
            v[p] = 1
            v[q] = 1
            del A[p][0]
            del A[q][0]
        
    if A == empty:
        print(day)
        break
    
    if v == default:
        print(-1)
        break

### FIXED CODE ###

# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n)-1 for n in input().split() ] )

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = []
q0 = []

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.append( match(i,j) )
            
day = 0

while True:
    day += 1
    for M in q:
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.append(m)
        NEXT[M] = []
    q = q0
    q0 = []
    #print(NEXT)
    #print(before)
    if q == []:
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    len_S = len(S)
    L_d = 0
    L_min_d = 0
    R_d = 0
    R_min_d = 0
    for i in range(len_S):
        if S[i] == '(':
            L_d += 1
        else:
            L_d -= 1
            L_min_d = min(L_min_d, L_d)
        if S[len_S-i-1] == ')':
            R_d += 1
        else:
            R_d -= 1
            R_min_d = min(R_min_d, R_d)
    if L_d >= 0:
        L.append((L_d, L_min_d))
    else:
        R.append((R_d, R_min_d))

L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1], reverse=True)

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

print(ans)

### FIXED CODE ###

# F - Bracket Sequencing

N = int(input())
L = []
R = []
for _ in range(N):
    S = list(str(input()))
    len_S = len(S)
    L_d = 0
    L_min_d = 0
    R_d = 0
    R_min_d = 0
    for i in range(len_S):
        if S[i] == '(':
            L_d += 1
        else:
            L_d -= 1
            L_min_d = min(L_min_d, L_d)
        if S[len_S-i-1] == ')':
            R_d += 1
        else:
            R_d -= 1
            R_min_d = min(R_min_d, R_d)
    if L_d >= 0:
        L.append((L_d, L_min_d))
    else:
        R.append((R_d, R_min_d))

L.sort(key=lambda x: x[1], reverse=True)
R.sort(key=lambda x: x[1], reverse=True)

ans = 'Yes'
l_now = 0
for d, min_d in L:
    if l_now + min_d < 0:
        ans = 'No'
        break
    else:
        l_now += d

r_now = 0
for d, min_d in R:
    if r_now + min_d < 0:
        ans = 'No'
        break
    else:
        r_now += d

if l_now != r_now:
    ans = 'No'

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

#!/usr/bin/env python3

def gcd(m, n):
    x = max(m, n)
    y = min(m,n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        temp = gcd(i, j)
        for k in range(1, K+1):
            ans += gcd(temp, k)
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import math

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        temp = math.gcd(i, j)
        for k in range(1, K+1):
            ans += math.gcd(temp, k)

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

import math
Primes = {2}
Sim = [0 for i in range(100002)]

for i in range(3, 100001):
    if i % 2 == 0:
        Sim[i] = Sim[i-1]
    else:
        for p in Primes:
            if i % p == 0:
                Sim[i] = Sim[i-1]
                break
        else:
            Primes |= {i}
            if (i+1)//2 in Primes:
                Sim[i] = Sim[i-1] + 1
            else:
                Sim[i] = Sim[i-1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(Sim[r] - Sim[l-1])

### FIXED CODE ###

Num = [int(i) for i in range(2, 100001)]
Primes = [True for i in range(100001)]
Sim = [0 for i in range(100001)]

for i in range(2, 100001):
    if Primes[i] == True:
        j = i * 2
        while j < 100001:
            Primes[j] = False
            j += i

for i in range(3, 100001):
    if Primes[i] and Primes[(i+1)//2]:
        Sim[i] = Sim[i-1] + 1
    else:
        Sim[i] = Sim[i-1]

Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(Sim[r] - Sim[l-1])
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import deque
    N, M = MI()
    fri_list = [[-1] for _ in range(N)]
    for i in range(M):
        a, b = MI()
        fri_list[a - 1].append(b)
        fri_list[b - 1].append(a)

    def bfs(u, n, g, A, B):
        queue = deque([u])
        d = [None] * (n + 1)  # uからの距離の初期化
        d[u] = 0  # 自分との距離は0
        A.append(u)
        while queue:
            v = queue.popleft()
            for i in g[v - 1]:
                if i == -1:
                    continue
                if d[i] is None:
                    d[i] = 1
                    B[i] = 1
                    queue.append(i)
                    A.append(i)

    group_list = []
    num_list = [0] * (N + 1)
    for i in range(1, N + 1):
        if num_list[i] == 0:
            G = []
            bfs(i, N, fri_list, G, num_list)
            group_list.append(G)

    len_list = []
    for l in group_list:
        x = len(l)
        len_list.append(x)
    ans = max(len_list)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import deque
    N, M = MI()
    fri_list = [[] for _ in range(N)]
    for i in range(M):
        a, b = MI()
        fri_list[a - 1].append(b - 1)
        fri_list[b - 1].append(a - 1)

    #print(fri_list)
    group_list = []
    num_list = [0] * N
    for i in range(0, N):
        if num_list[i] == 0:
            num_list[i] = 1
            #print(i, 'i')
            cnt = 1
            queue = deque([i])
            while queue:
                v = queue.popleft()
                #print(v, 'v')
                for j in fri_list[v]:
                    #print(j, 'j')
                    if num_list[j] == 0:
                        num_list[j] = 1
                        queue.append(j)
                        cnt += 1
            group_list.append(cnt)

    ans = max(group_list)
    print(ans)

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

import numpy as np
N,K = map(int,input().split())
LR = []
for _ in range(K):LR.append(list(map(int,input().split())))
MOD = 998244353
dp = np.zeros(N,"i8")
dp[0] = 1
for i in range(N):
  for L,R in LR:
    if i+L<N:
      dp[i+L:i+R+1] += dp[i]
      dp[i+L:i+R+1] %= MOD
print(dp[-1])

### FIXED CODE ###

N,K = map(int,input().split())
LR = []
for _ in range(K): LR.append(list(map(int,input().split())))
MOD = 998244353
dp = [0]*(N+1)
dp[0] = 1
for i in range(N):
  for L,R in LR:
    if i+L<N: dp[i+L] += dp[i]
    if i+R+1<N: dp[i+R+1] -= dp[i]
  if i>0: dp[i+1] = (dp[i+1]+dp[i])%MOD
print(dp[-1])