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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache
INF = float("inf")

MOD = 998244353  # type: int


def main():
    A, B, C, D = map(int, input().split())

    @lru_cache(maxsize=None)
    def f(a, b):
        if a < A or b < B:
            return 0
        if a == A and b == B:
            return 1
        elif a == A:
            return pow(A, b-B, MOD)
        elif b == B:
            return pow(B, a-A, MOD)
        ans = (f(a-1, b)*b) % MOD
        ans += (f(a, b-1)*a) % MOD
        ans -= (f(a-1, b-1)*(a-1)*(b-1)) % MOD
        ans %= MOD
        return ans

    print(f(C, D))

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache
INF = float("inf")

MOD = 998244353  # type: int


def main():
    A, B, C, D = map(int, input().split())
    DP = [[1]*(D-B+1) for _ in range(C-A+1)]

    for i in range(C-A+1):
        for j in range(D-B+1):
            if i == j == 0:
                continue
            DP[i][j] = 0
            if 0 <= i-1:
                DP[i][j] += (DP[i-1][j]*(j+B)) % MOD
                DP[i][j] %= MOD
            if 0 <= j-1:
                DP[i][j] += (DP[i][j-1]*(i+A)) % MOD
                DP[i][j] %= MOD
            if 0 <= i-1 and 0 <= j-1:
                DP[i][j] -= (DP[i-1][j-1]*(i+A-1)*(j+B-1)) % MOD
                DP[i][j] %= MOD
            # print(i, j, DP[i][j])
    print(DP[-1][-1] % MOD)
    # print(DP)

    # @lru_cache(maxsize=None)
    # def f(a, b):
    #     if a < A or b < B:
    #         return 0
    #     if a == A and b == B:
    #         return 1
    #     elif a == A:
    #         return pow(A, b-B, MOD)
    #     elif b == B:
    #         return pow(B, a-A, MOD)
    #     ans = (f(a-1, b)*b) % MOD
    #     ans += (f(a, b-1)*a) % MOD
    #     ans -= (f(a-1, b-1)*(a-1)*(b-1)) % MOD
    #     ans %= MOD
    #     return ans

    # print(f(C, D))

    return


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

def sieve(n):
    num = [True] * n
    num[0] = num[1] = False
    for i in range(2,int(n**0.5)+1):
        if num[i]:
            for j in range(i**2, n, i):
                num[j] = False
    return [i for i in range(2, n) if num[i]]


while True:
	n = int(input())
	if n == 0: break
	print(sum(sieve(n * 100)[:n]))

### FIXED CODE ###

def sieve(n):
    num = [True] * n
    num[0] = num[1] = False
    for i in range(2,int(n**0.5)+1):
        if num[i]:
            for j in range(i**2, n, i):
                num[j] = False
    return [i for i in range(2, n) if num[i]]

prime = sieve(110000)

while True:
	n = int(input())
	if n == 0: break
	print(sum(prime[:n]))
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
  l=list(map(str,input().split()))
  if l[0]=="1":
    s=s[::-1]
  elif l[1]=="1":
    s=l[2]+s
  else:
    s=s+l[2]
print(s)

### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
l = [list(input().split()) for i in range(q)]
c=0
for i in range(q):
  if l[i][0]=="1":
    c+=1
  elif c%2==0 and l[i][1]=="1":
    s.appendleft(l[i][2])
  elif c%2==0:
    s.append(l[i][2])
  elif c%2==1 and l[i][1]=="1":
    s.append(l[i][2])
  else:
    s.appendleft(l[i][2])
s=list(s)
if c%2==1:
  s=s[::-1]
print(*s, sep="")
### BUGGY CODE ###

import math 
n=[int(_) for _ in input().split()]
step = math.ceil(n[1]/n[0])
ans=0
for i in range(1,n[2]+1,step):
  tmp=math.floor(n[0]*i/n[1])-(n[0]*math.floor(i/n[1]))
  if tmp>ans:
    ans=tmp
print(ans)


### FIXED CODE ###

import math
a,b,n=map(int,input().split())
c=min(b-1,n)
f=math.floor(a*c/b)
print(f)
### BUGGY CODE ###

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

for i in range(N):
    print(a.count(i+1))

### FIXED CODE ###

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

N,Q = [int(i) for i in input().split()]
S = str(input())
lrlist = []
for i in range(Q):
    lrlist.append([int(i)-1 for i in input().split()])

#print(S)
#print(lrlist)

Asite = []
for i in range(len(S)-1):
    if S[i]=="A" and S[i+1]=="C":
        Asite.append(i)


for l,r in lrlist:
    ans = 0
    for i in Asite:
        if l <= i and i+1 <= r:
            ans+=1
    print(ans)

### FIXED CODE ###

N,Q = [int(i) for i in input().split()]
S = str(input())
lrlist = []
for i in range(Q):
    lrlist.append([int(i)-1 for i in input().split()])

#print(S)
#print(lrlist)

Asite = [0]
for i in range(1,len(S)):
    if S[i-1]=="A" and S[i]=="C":
        Asite.append(Asite[-1]+1)
    else:
        Asite.append(Asite[-1])


for l,r in lrlist:
    print(Asite[r]-Asite[l])
### BUGGY CODE ###

k = int(input())
ans=0
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += gcd(a,gcd(b,c))
print(ans)

### FIXED CODE ###

k = int(input())
ans=0
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x
 
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += gcd(a,gcd(b,c))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


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

dp = [0]*(w + 1)
for i in range(n):
    for j in range(w + 1)[::-1]:
        if j - info[i][0] < 0:
            break
        else:
            dp[j] = max(dp[j], dp[j - info[i][0]] + info[i][1])
print(dp[w])

### FIXED CODE ###

n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]

## dp[i][j]:i番目までのアイテムを重さjのナップサックに詰めるときの最大価値
dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if j-info[i][0]>=0:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-info[i][0]]+info[i][1])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n][w])
### BUGGY CODE ###

n,C,*H=map(int,open(0).read().split());
dp=[0];
P=[0];
f=lambda I,h:dp[I]+H[I]*(H[I]-2*h)
c=lambda x,y,z:(H[y]-H[x])*(f(y,0)-f(z,0))>(H[z]-H[y])*(f(x,0)-f(y,0))
for i in range(1,n):
    h=H[i]
    while len(P)>1 and f(P[0],h)>f(P[1],h):P.pop(0)
    dp+=[f(P[0],h)+h**2+C]
    while len(P)>1 and c(P[-2],P[-1],i):P.pop()
    P+=[i]
print(dp[-1])

### FIXED CODE ###

n,C,*H=map(int,open(0).read().split());
dp=[0];
P=[0];
def f(I,h):
    return dp[I]+H[I]*(H[I]-2*h)
def c(x,y,z):
    return (H[y]-H[x])*(f(y,0)-f(z,0))>(H[z]-H[y])*(f(x,0)-f(y,0))
for i in range(1,n):
    while len(P)>1 and f(P[0],H[i])>f(P[1],H[i]):P.pop(0)
    dp+=[f(P[0],H[i])+H[i]**2+C]
    while len(P)>1 and c(P[-2],P[-1],i):P.pop()
    P+=[i]
print(dp[-1])
### BUGGY CODE ###

def dp(n,W,w,p,cache):
  
  if n==0 or W==0:
    return 0
  elif cache.get((n,W)):
    return cache[(n,W)]
  else:
    if w[n-1]<=W:
      cache[(n,W)]=max(p[n-1]+dp(n-1,W-w[n-1],w,p,cache),dp(n-1,W,w,p,cache))
      return cache[(n,W)]
    else:
      cache[(n,W)]=dp(n-1,W,w,p,cache)
      return cache[(n,W)]
n,W=map(int,input().split())
weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p)
print(dp(n,W,weight,profit,dict()))


### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
### BUGGY CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

K = readInt()
def gcd(a,b,c):
	return math.gcd(math.gcd(a,b),c)
ans=0
for a in range(1,K+1):
	for b in range(1,K+1):
		for c in range(1,K+1):
			ans+=gcd(a,b,c)

print(ans)

### FIXED CODE ###

import math
import queue
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def printQueue(q):
	r=q
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)

K = readInt()
d = defaultdict(int)
ans=0
for a in range(1,K+1):
	for b in range(1,K+1):
		x = math.gcd(a,b)
		for c in range(1,K+1):
			ans+=math.gcd(x,c)

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

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

### FIXED CODE ###

k,s=map(int,input().split(" "))
c=0
for i in range(k+1):
  for j in range(k+1):
    if s-i-j<=k and s-i-j>=0:
      c+=1

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

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = {}
def find(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')



### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].append(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append([])
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-1
        for k in blk[j-1]:
            if k in unii:
                cj-=1
        seq[j-1]=cj

s=list(map(str,seq))

s=" ".join(s)

print(s)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)

def dfs(x):
    if seen[x-1]==0:
        uni[cnt].add(x)
        seen[x-1]=1
        for i in fri[x-1]:
            dfs(i)
    

n,m,k=map(int,input().split())

fri=[[] for i in range(n)]
blk=[[] for i in range(n)]

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

for i in range(k):
    c,d=map(int,input().split())
    blk[c-1].append(d)
    blk[d-1].append(c)


seen=[0 for i in range(n)]

uni=[]
cnt=0
for i in range(1,n+1):
    if seen[i-1]==0:
        uni.append(set())
        dfs(i)
        cnt+=1

seq=[0 for i in range(n)]

for unii in uni:
    for j in unii:
        cj=len(unii)-len(fri[j-1])-len(unii&set(blk[j-1]))-1
        seq[j-1]=cj

print(*seq)
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
C=Counter(a)
#print(C)
for i in range(n):
    D=C.copy()
    D[a[i]]-=1
    #print(D,C)
    ans=0
    for k,v in D.items():
        if v>=2:
            ans+=v*(v-1)//2
    print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
C=Counter(a)
#print(C)
total=0
for k,v in C.items():
    if v>=2:
        total+=v*(v-1)//2
#print(total)
for i in range(n):
    V=C[a[i]]
    ans=total-(V*(V-1))//2+((V-1)*(V-2))//2
    print(ans)
### BUGGY CODE ###

N = int(input())

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = {color for color in range(1, k + 1)}
usedcolor_sets = [set() for _ in range(N)]
colored = {}

for v in range(N):
  unused_colors = colors - usedcolor_sets[v]  
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = unused_colors.pop()
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor_sets[edge].add(color)

print(k)

for a, b in edges:
  print(colored[(a, b)])
  

### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [None for _ in range(N)]
colored = {}

def colors_except(x):
  for c in colors:
    if c == x:
      continue
    yield c

for v in range(N):
  unused_colors = colors_except(usedcolor[v])
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = next(unused_colors)
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

for a, b in edges:
  print(colored[(a, b)])
### BUGGY CODE ###

n, res = int(input()), 1
List = list(map(int, input().split()))
if 0 in List:
    print(0)
    quit()
for x in List:
    res *= x
    if res > 10**18:
        res = -1
print(res)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
res = 1
if 0 in List:
    print(0)
    quit()
for x in List:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
ans=""
for i in range(n):
  b.append(a[i])
  b.reverse()
print(*b)

### FIXED CODE ###

from collections import deque
n=int(input())
a=list(map(int,input().split()))
b=deque(maxlen=2*10**5)
if n%2==0:
  for i in range(n):
    if i%2==1:
      b.appendleft(a[i])
    else:
      b.append(a[i])
else:
  for j in range(n):
    if j%2==0:
      b.appendleft(a[j])
    else:
      b.append(a[j])
print(*b)
### BUGGY CODE ###

def line(N, X, Y):
    X = X - 1
    Y = Y - 1

    queue = [(a, a) for a in range(N - 1)]
    visited = set()

    for i in range(N - 1):
        new_queue = []

        def add_to_queue(x, y):
            if y == N or y < 0:
                return
            if x == N or x < 0:
                return
            if x == y:
                return

            if x > y:
                x, y = y, x

            t = (x, y)
            if t not in visited:
                new_queue.append(t)
                visited.add(t)

        for q in queue:
            add_to_queue(q[0], q[1] + 1)
            add_to_queue(q[0], q[1] - 1)
            add_to_queue(q[0] + 1, q[1])
            add_to_queue(q[0] - 1, q[1])

            if q[1] == X:
                add_to_queue(q[0], Y)
            if q[1] == Y:
                add_to_queue(q[0], X)
            if q[0] == X:
                add_to_queue(Y, q[1])
            if q[0] == Y:
                add_to_queue(X, q[1])

        print(len(new_queue))
        # print(f"{len(new_queue)} {new_queue}")
        queue = new_queue


N, X, Y = map(int, input().split())
line(N, X, Y)

# line(5, 2, 4)
# print()
# line(3, 1, 3)
# print()
# line(7, 3, 7)
# print()
# line(10, 4, 8)


### FIXED CODE ###

# https://atcoder.jp/contests/abc160/tasks/abc160_d
N, X, Y = map(int, input().split())

visited = set()

# special case: first advance
for i in range(N - 1):
    visited.add((i, i + 1))
visited.add((X - 1, Y - 1))

print(len(visited))

next_items = visited.copy()
for _ in range(N - 2):
    candidates = []

    for point in next_items:
        x, y = point

        if (x - 1, y) not in visited and x - 1 >= 0:
            visited.add((x - 1, y))
            candidates.append((x - 1, y))

        if (x + 1, y) not in visited and x + 1 != y:
            visited.add((x + 1, y))
            candidates.append((x + 1, y))

        if (x, y - 1) not in visited and x != y - 1:
            visited.add((x, y - 1))
            candidates.append((x, y - 1))

        if (x, y + 1) not in visited and y + 1 < N:
            visited.add((x, y + 1))
            candidates.append((x, y + 1))

    print(len(candidates))
    next_items = candidates
### BUGGY CODE ###

from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = []
colors = [1 for _ in range(1, N + 1)]
used_colors = [[] for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.popleft()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].append(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.append(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1
        
print(max_col)
for c in colors[1:]:
    print(c)


### FIXED CODE ###

from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = set()
colors = [1 for _ in range(1, N + 1)]
used_colors = [set() for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.pop()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].add(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.add(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)
### BUGGY CODE ###

S = input()
digits = list(map(int,S))
# S = S[::-1]→これが時間かかる

# i~nまでの値をmod2019したときの数
ls = [0for i in range(2019)]

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in reversed(digits):
    x += i*pow10
    count += ls[x%2019]
    ls[x%2019] += 1
    pow10 *= 10

# for x in ls:
#     count += x*(x-1)/2

print(int(count))



### FIXED CODE ###

S = input()
digits = list(map(int,S))
# S = S[::-1]→これが時間かかる

# i~nまでの値をmod2019したときの数
# ls = [0for i in range(2019)]
ls = [0] * 2019

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in reversed(digits):
    x += i*pow10
    x %= 2019
    count += ls[x]
    ls[x] += 1
    pow10 *= 10
    pow10 %= 2019

# for x in ls:
#     count += x*(x-1)/2

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

from collections import Counter

N = int(input())
As = list(map(int, input().split()))
count = sorted(Counter(As).items(), key = lambda x: x[0])
divider = set()


ans = 0
for num, c in count:
  if c > 1:
    divider.add(num)
    continue
  for i in divider:
    if num % i == 0:
      break
  else:
    divider.add(num)
    ans += 1
  
print(ans)

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)
### BUGGY CODE ###

from fractions import gcd

def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    lcm = A[0]
    MOD = 10**9 + 7
    for a in A:
        lcm = (lcm // gcd(lcm,a) * a)
    res = 0
    for a in A:
        res = (res + lcm // a) % MOD
    print(res)
main()
    

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
lcm = A[0]
MOD = 10**9 + 7
for a in A:
    lcm = (lcm // gcd(lcm,a) * a)
res = 0
for a in A:
    res += lcm //a
print(res % MOD)