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

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    visited = [False] * N
    E = [[] for i in range(N)]
    nums = [set() for i in range(N)] 
    ans = [None] * (N-1)
    
    for i in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append((b-1, i))
        E[b-1].append((a-1, i))
        
    ans_ = max([len(e) for e in E])
    G = set(i for i in range(ans_))
    
    q = [0]
    
    while q:
        v = q.pop(0)
        
        if visited[v]: continue
    
        visited[v] = True
        
        use_nums = list(G - nums[v])
        for u, idx in E[v]:
            if visited[u]: continue
            
            n = use_nums.pop(0)
            ans[idx] = str(n+1)
            nums[u].add(n)
            q.append(u)
            
    print(ans_)
    print('\n'.join(ans))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    G = [[] for i in range(N)]
    ans = [None] * (N-1)
    
    for i in range(N-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        
        G[a].append((b, i))
        G[b].append((a, i))
        
    q = [(0, -1)]
    
    visited = [False] * N
    cur = 0
    
    while q and cur < N:
        v, c = q.pop(0)
    
        if visited[v]: continue
        visited[v] = True
        cur += 1
        
        k = 0
        for u, idx in G[v]:
            if visited[u]: continue
            if c == k: k += 1
            
            ans[idx] = k
            q.append((u, k))
            k += 1
            
    print(max(ans)+1)
    for a in ans: print(a+1)
     
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = sorted(inpl())
lmx = len(bin(a[-1])) - 2
cnt = [[0,0] for _ in range(lmx)]
for i in range(n):
    tmp = bin(a[i])[::-1]
    ln = len(tmp)-2
    for j in range(lmx):
        tt = 0
        if j < ln:
            tt = int(tmp[j])
        cnt[j][tt] += 1
# print(cnt)
res = 0
for i,bit in enumerate(cnt):
    x,y = bit
    res += x*y*pow(2,i)
    res %= mod
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
a.sort()
ln = len(bin(a[-1])) - 2
bit = [defaultdict(int) for i in range(ln)]
res = 0
for i in a:
    tmp = bin(i)
    for _,j in enumerate(tmp[:1:-1]):
        # print(_,j)
        bit[_][j] += 1
# pprint.pprint(bit)
for i,j in enumerate(bit):
    x = j['0']
    y = j['1']
    if x+y < n:
        x = n - y
    # print(i,x,y)
    c = pow(2,i)
    res += x * y * c
    res %= mod
print(res)
### BUGGY CODE ###

N = int(input())
V = [int(n) for n in input().split()]
C = [int(n) for n in input().split()]
B = []
for i in range(N):
    B.append(V[i] - C[i])
#print(B)

max_profit = 0
for i in range(2**N):
    
    profit = 0
    for j in range(N):
        if i & (1 << j):
            profit += B[j]
    
    max_profit = max(max_profit, profit)

print(max_profit)



### FIXED CODE ###

N = int(input())
V = [int(n) for n in input().split()]
C = [int(n) for n in input().split()]

profit = 0
for i in range(N):
    if V[i] - C[i] >= 0:
        profit += V[i] - C[i]

print(profit)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
tmp = [1 for i in range(N-K+1)]

for i in range(K, N+1):
    for j in range(K):
        tmp[i-K] *= A[i-K+j]

for i in range(1, N-K+1):
    if tmp[i-1] < tmp[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(K, N):
    if A[i-K] < A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0

while a != []:
    ans += a[-2]
    a = a[1:-2]
print(ans)

### FIXED CODE ###

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

a.sort(reverse=True)
ans = 0
count = 0
for i in range(1, N*3+1, 2):
    if count == N:
        break
    else:
        ans += a[i]
        count += 1

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

def myAnswer(N:int,A:list) -> int:
   for bit in range(2**N - 1):
      i = 1
      counter = 0
      for n in range(N): 
         if(bit & (1<<n)):
            counter += 1
            continue
         else:
            if( A[n] != i):
               break
            i+=1

      else:
         return counter
   return -1


def modelAnswer():
   tmp=1
def main():
   N = int(input())
   A = list(map(int,input().split()))
   print(myAnswer(N,A[:]))

if __name__ == '__main__':
   main()

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
counter=0
n=1
for a in A:
    if(a == n):
        n+=1
    else:
        counter+=1

print(counter) if(n != 1) else print(-1)
### BUGGY CODE ###

#Code by Sounak, IIESTS
#------------------------------warmup----------------------------

import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict


BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
    
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
     
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
  
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#-------------------game starts now-----------------------------------------------------
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
m=max(a)+1
g=a[0]
d=defaultdict(int)
for i in a:
    g=math.gcd(g,i)
    d[i]+=1
if g>1:
    print("not coprime")
else:
    p=[0]*(m)
    ch=0
    for i in range (2,m):
        if p[i]==1:
            continue
        p[i]=1
        ans=0
        for j in range (i,m,i):
            ans+=d[j]
        if ans>1:
            ch=1
            break
    if ch==1:
        print("setwise coprime")
    else:
        print("pairwise coprime")

### FIXED CODE ###

import math
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
m=max(a)+1
g=a[0]
d=dict()
for i in a:
    g=math.gcd(g,i)
    if i in d:
        d[i]+=1
    else:
        d[i]=1
if g>1:
    print("not coprime")
else:
    p=[0]*(m)
    ch=0
    for i in range (2,m):
        if p[i]==1:
            continue
        p[i]=1
        ans=0
        for j in range (i,m,i):
            if j in d:
                ans+=d[j]
        if ans>1:
            ch=1
            break
    if ch==1:
        print("setwise coprime")
    else:
        print("pairwise coprime")
### BUGGY CODE ###

l,r=map(int,input().split())
count=2019
for i in range(l,r):
    for j in range(i+1,r+1):
        count=min(count,(i*j)%2019)
        if i*j%2019==0:
            break

print(count)


### FIXED CODE ###

l,r=map(int,input().split())
count=2019
for i in range(l,r):
    for j in range(i+1,r+1):
        count=min(count,(i*j)%2019)
        if i*j%2019==0:
            break
    if i*j%2019==0:
        break
print(count)
### BUGGY CODE ###

import numpy as np

n = int(input())

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

x = {}
y = {}

ans = 0

# print(x)
# print(y)

for i in range(n):
  x.setdefault((i+a[i]), []).append(i) 
  y.setdefault((i-a[i]), []).append(i)

z = list(set(x.keys()) & set(y.keys()))

# print(x)
# print(y)
# print(z)

for i in z:
  for j in range(len(x[i])):
    # print(x[i])
    # print(x[i][j])
    # print(y[i])
    # print(sum(x[i][j] < y[i][0]))
    ans += sum(1 for k in y[i] if x[i][j] < k)

print(ans)

### FIXED CODE ###

import numpy as np

n = int(input())

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

x = {}
y = {}

ans = 0

for i in range(n):
  x.setdefault((i+a[i]), []).append(i) 
  y.setdefault((i-a[i]), []).append(i)

z = list(set(x.keys()) & set(y.keys()))

# print(x)
# print(y)
# print(z)

for i in z:
  if x[i][len(x[i])-1] < y[i][0]:
    n = len(y[i]) * len(x[i])
    ans += n
    # print(x[i])
    # print(y[i])
    # print(n)
    # print(ans)

  else:
    for j in range(len(x[i])):
      # print(x[i])
      # print(x[i][j])
      # print(y[i])
      ans += sum(1 for k in y[i] if x[i][j] < k)

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

# http://drken1215.hatenablog.com/entry/2020/01/26/225000

H, N = map(int, input().split())
dp = [float("inf") for i in range(H+1)]

dp[0] = 0

for i in range(N):
  a, b = map(int, input().split())
  
  for j in range(H):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


print(dp[H])

### FIXED CODE ###

H, N = map(int, input().split())
dp = [10**8 for i in range(H+1)]

dp[0] = 0

for i in range(N):
  a, b = map(int, input().split())
  
  for j in range(H):
    dp[min(j+a, H)] = min(dp[min(j+a, H)], dp[j] + b)


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

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
  print(a.index(i+1) + 1,end = " ")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
for i in range(n):
    ans[a[i]-1] = str(i + 1)
print(" ".join(ans))
### BUGGY CODE ###

import math

MOD = int(10**9 + 7)

def egcd(a, b):
    if a ==  0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b%a, a)
        return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("No inverse exists")
    else:
        return x % m

def combination(n, r):
    return math.factorial(n) * modinv(math.factorial(r), MOD) * modinv(math.factorial(n-r), MOD)
    # return math.factorial(n) // math.factorial(r) // math.factorial(n-r)

N, M, K = map(lambda x: int(x), input().split())

ans = 0

k = combination(N*M-2, K-2)

for d in range(1, N):
    ans += d * k * M * M * (N - d)

for d in range(1, M):
    ans += d * k * N * N * (M - d)

print(ans % MOD)


### FIXED CODE ###

import math

MOD = int(10**9 + 7)

def egcd(a, b):
    if a ==  0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b%a, a)
        return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("No inverse exists")
    else:
        return x % m

def combination(n, r):
    return math.factorial(n)%MOD * modinv(math.factorial(r), MOD) * modinv(math.factorial(n-r), MOD) % MOD
    # return math.factorial(n) // math.factorial(r) // math.factorial(n-r)

N, M, K = map(lambda x: int(x), input().split())

ans = 0

k = combination(N*M-2, K-2)

for d in range(1, N):
    ans += (d * k * M * M * (N - d))%MOD

for d in range(1, M):
    ans += (d * k * N * N * (M - d))%MOD

print(ans % MOD)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

for i in range(n):
    visited = [False] * n
    i_good = es1[i]
    i_bad = es2[i]
    visited
    queue = deque()
    queue.extend(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans[i] += 1
            visited[next_] = True
            queue.extend(es1[next_])

    ans[i] -= 1
    if ans[i] < 0:
        ans[i] = 0

print(*ans, sep=' ')

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def members(self, x):
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m, k = map(int, input().split())
uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)
    uf.union(a,b)

es_block_in_union = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    if uf.is_same(c,d):
        es_block_in_union[c].append(d)
        es_block_in_union[d].append(c)


ans = [0]*n
for i in range(n):
    ans[i] =  uf.size(i) - len(es_block_in_union[i])  - len(es1[i]) -1

print(*ans, sep=' ')
### BUGGY CODE ###

N,Q=map(int,input().split())
Ss=[i for i in input()]
#S = input()
for i in range(Q):
    l,r = map(int,input().split())
    count = 0
    Sscopy = Ss[l-1:r]
    anslist="".join(Sscopy).split("AC")
    print(len(anslist)-1)

### FIXED CODE ###

N,Q=map(int,input().split())
Ss=[i for i in input()]
counterlist=[0]*N
for s in range(len(Ss)-1):
    if Ss[s]=="A" and Ss[s+1]=="C":
        counterlist[s+1]=1
for c in range(len(counterlist)-1):
    counterlist[c+1]+=counterlist[c]
for i in range(Q):
    l,r = map(int,input().split())
    print(counterlist[r-1]-counterlist[l-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

N=int(input())

node=[[0] for i in range(N)]
#print(node)
q=[]
for i in range(N-1):
    a,b=map(int,input().split())
    q.append([a-1,b-1,i])

q.sort(key=lambda x:x[0])

ans=0
for index in range(len(q)):
    frm,to,num=q[index][0],q[index][1],q[index][2]
    for i in range(1,10**5+1):
        if (i in node[frm]) or (i in node[to]):
            pass
        else:
            node[frm].append(i)
            node[to].append(i)
            q[index].append(i)
            ans=max(ans,i)
            break
            
print(ans)
q.sort(key=lambda x:x[2])
for item in q:
    print(item[3])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

N=int(input())

q=[]

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

ans=[1]*N
ans[0]=0
#print(l)

for i in range(N-1):
    a,b=map(int,input().split())
    q.append([a-1,b-1])
    l[a-1].append(b-1)

mx=0
for index,item in enumerate(l):
    color=1
    while item:
        temp=item.pop(-1)
        if color==ans[index]:
            color+=1
        ans[temp]=color
        color+=1
    mx=max(color-1,mx)

print(mx)
for _,item in q:
    print(ans[item])
### BUGGY CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=int(i*(i-1)/2)
  print(res)

if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

x, y, z, k = map(int, input().split())
a_s = list(map(int, input().split()))
bs = list(map(int, input().split()))
cs = list(map(int, input().split()))
a_s.sort(reverse=True)
bs.sort(reverse=True)
cs.sort(reverse=True)

list = []
i = -1
minlist = 0
flag = True
for a in a_s:
    if minlist > (a + bs[0] + cs[0]):
        break
    for b in bs:
        if minlist > (a + b + cs[0]):
            break
        for c in cs:
            list.append(a + b + c)
            i += 1
            if flag and i > k:
                minlist = min(list)
                flag = False
            if minlist > list[i]:
                break
list.sort(reverse=True)
for i in range(k):
    print(list[i])


### FIXED CODE ###

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

ab = []
for ai in a:
  for bi in b:
    ab.append(ai + bi)
ab.sort(reverse = True)

abc = []

for abi in ab[:k]:
  for ci in c:
    abc.append(abi + ci)
abc.sort(reverse = True)

for abci in abc[:k]:
  print(abci)
### BUGGY CODE ###

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

AB = [list(map(int, input().split())) for _ in range(N)]

d = [0] + [10**18] * H

for hp in range(1, H + 1):
    for ab in AB:
        # print(ab)
        hp_remain = hp - ab[0]
        if hp_remain < 0: hp_remain = 0
        # print(hp_remain)
        c = d[hp_remain] + ab[1]
        if c < d[hp]: d[hp] = c

print(d[H])




### FIXED CODE ###

import numpy as np


H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
a, b = np.array(AB, dtype=np.int64).reshape(N, 2).T

d = np.zeros(H + 1, dtype=np.int64)

for hp in range(1, H + 1):
    c = d[np.maximum(hp - a, 0)] + b
    d[hp] = np.amin(c)

print(d[H])
### BUGGY CODE ###

from sys import stdin
N,Y=list(map(int,stdin.readline().strip().split()))
man=Y//10000
gosen=Y//5000

for i in range(man+1,-1,-1):
    if i>N:continue
    for j in range(0,gosen+1):
        if i+j > N or  10000*i+j*5000>Y : break
        for k in range(0,N-(i+j)+1):
            if i + j+k > N: break
            goukei=10000*i+j*5000+k*1000
            if goukei==Y and (i+j+k)==N:
                print(i,j,k)
                exit()

print(-1,-1,-1)


### FIXED CODE ###

from sys import stdin
N,Y=list(map(int,stdin.readline().strip().split()))
a=0
b=0
c=0
i=0
for i in range(N+1):
    for j in range(N+1):
        z=N-i-j
        if i*1000+5000*j+z*10000==Y and z>=0:
            print("%d %d %d" %(z,j,i))
            exit()
print("-1 -1 -1")
### BUGGY CODE ###

import collections
s = input()
n = len(s)
mod_list = [0]

T = 0
for i in range(n):
    T += int(s[-1-i])*(10**i)%2019
    T = T%2019
    mod_list.append(T)

res = collections.Counter(mod_list)
cnt = 0
for d in res:
    cnt += int(res[d]*(res[d]-1)/2)
print(cnt)

### FIXED CODE ###

import collections
s = input()
n = len(s)
mod_list = [0]

T = 0
for i in range(n):
    T += int(s[-1-i])*pow(10, i, 2019)%2019
    T = T%2019
    mod_list.append(T)

res = collections.Counter(mod_list)
cnt = 0
for d in res.values():
    cnt += int(d*(d-1)/2)
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import functools
from itertools import permutations


@functools.lru_cache(maxsize=None)
def cost1(i, color):
    cost = 0
    for r in range(N):
        for c in range(N):
            if (r + c) % 3 == i:
                cost += D[G[r][c] - 1][color - 1]

    return cost


def cost2(comb):
    cost = 0
    for i, color in enumerate(comb):
        cost += cost1(i, color)

    return cost


N, C = map(int, input().split())
D = [[int(_) for _ in input().split()] for i in range(C)]
G = [[int(_) for _ in input().split()] for i in range(N)]
combs = permutations(range(1, C + 1), 3)
min_cost = min([cost2(comb) for comb in combs])
print(min_cost)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N, C = map(int, input().split())

D = []
for c in range(C):
    D.append([int(d) for d in input().split()])

Gmod = [[0 for i in range(C)] for i in range(3)]
for n in range(N):
    for m, g in enumerate(input().split()):
        Gmod[(n + m) % 3][int(g) - 1] += 1

K = []
for c0 in range(C):
    d0 = sum([Gmod[0][c] * D[c][c0] for c in range(C)])
    for c1 in [i for i in range(C) if not i == c0]:
        d1 = sum([Gmod[1][c] * D[c][c1] for c in range(C)])
        for c2 in [i for i in range(C) if (not i == c0) and (not i == c1)]:
            d2 = sum([Gmod[2][c] * D[c][c2] for c in range(C)])
            K.append(d0 + d1 + d2)

print(min(K))
### BUGGY CODE ###

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    pt[0]=1
    for i in range(n):
        for l,r in lrs:
            pt[i+l:i+r+1]=([pt[i]]*(r-l+1)+pt[i+l:i+r+1])%MOD
    
    print(pt[n-1]%MOD)


if __name__=='__main__':
    do()

### FIXED CODE ###

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    rui=np.array([0]*((2*n)+1))
    pt[n-1]=1
    rui[n-1]=1
    for i in range(n):
        nt=n-1+i
        for l,r in lrs:
            pt[nt]=(pt[nt]-rui[nt-r-1]+rui[nt-l])%MOD
        rui[nt]=(rui[nt-1]+pt[nt])%MOD
    print(pt[2*n-2]%MOD)
    #print(pt)
    #print(rui)

    
    #print(pt[n-1]%MOD)


if __name__=='__main__':
    do()