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

Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1
#print(sorted(Ps))
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = 0
  for i in range(l, r+1, 2):
    if i in Ps and (i+1)//2 in Ps:
      re += 1
  print(re)


### FIXED CODE ###

Ps = set()
M = [False]*100001
p = 2
while p <= 100000:
  if not(M[p]):
    Ps.add(p)
    for i in range(p, 100000, p):
      M[i] = True
  p += 1
#print(sorted(Ps))
r = 0
Ss = [0]*100001
for i in range(100000):
  if i%2 == 1 and i in Ps and (i+1)//2 in Ps:
    r += 1
  Ss[i] = r
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  re = Ss[r]-Ss[l-1]
  print(re)
### BUGGY CODE ###

ss =[1 if s=='B' else 0 for s in input()]

def babble_sort(arr,ans):
    length = len(arr)

    for i in range(length):
        for j in reversed(range(i+1, length)):
            if arr[j-1] > arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
                ans+=1
    return ans

ans = babble_sort(ss,0)

print(ans)


### FIXED CODE ###

s = input() #sys.stdin.readlineは最後が改行

tmp =0
ans=0
for i in range(len(s)):
    if s[i]=='B':
        tmp+=1
    else:
        ans+=tmp

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

import collections

n = int(input())
a_list = list(map(int, input().split()))
for k in range(n):
    a_list_k = a_list.copy()
    del a_list_k[k]
    c = collections.Counter(a_list_k)
    ans = 0
    for i in c.values():
        ans += i*(i-1)//2
    print(ans)

### FIXED CODE ###

import collections

n = int(input())
a_list = list(map(int, input().split()))
c = collections.Counter(a_list)
ans = 0
for i in c.values():
    ans += i*(i-1)//2
for i in range(n):
    print(ans - (c[a_list[i]]-1))
### BUGGY CODE ###

def main():
    n = int(input())
    m = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            t = min(m[i][k] + m[k][j] if k != i and k != j else d + 1 for k in range(n))
            if t < d:
                print(-1)
                exit()
            if d < t:
                ans += d

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    m = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print(-1)
                    exit()
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


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

import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]*=-1
import heapq
heapq.heapify(a)
for i in range(m):
    # print(a)
    tmp=heapq.heappop(a)
    tmp=tmp*-1
    tmp=tmp//2
    tmp*=-1
    heapq.heappush(a,tmp)
    heapq.heapify(a)
print(sum(a)*-1)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
    a[i]*=-1
import heapq
heapq.heapify(a)
for i in range(m):
    # print(a)
    tmp=heapq.heappop(a)
    tmp=tmp*-1
    tmp=tmp//2
    tmp*=-1
    heapq.heappush(a,tmp)

print(sum(a)*-1)
### BUGGY CODE ###

N = int(input())

divisor = [N]
ans = 0

#Nの約数の列挙
for i in range(2,N+1,1):
    if i*i <= N:
        if N % i == 0:
            divisor.append(i)
            divisor.append(N//i)
    else:
        break

#N-1の約数の列挙
yakusuuu = [N-1]
for i in range(2,N,1):
    if i*i <= N:
        if N % i == 1:
            yakusuuu.append(i)
            yakusuuu.append((N-1)//i)

for i in yakusuuu:
    if N % i == 1:
        ans += 1

#print(divisor)
#print(yakusuuu)

n=N

for K in divisor:
    #print(K)
    for i in range(N):
        if n % K == 0:
            n = n//K#ここで全部N==1になっちゃう
        else:
            break
    

    if N == 1:
        ans += 1
        
    else:
        n %= K
        if n == 1:
            ans += 1 
    n =N
    
        




print(ans)


### FIXED CODE ###

N = int(input())

divisor = [N]
ans = 0

#Nの約数の列挙
for i in range(2,N+1,1):
    if i*i < N:
        if N % i == 0:
            divisor.append(i)
            divisor.append(N//i)
    elif i*i == N:
        divisor.append(i)
    else:
        break

#N-1の約数の列挙
yakusuuu = [N-1]
for i in range(2,N,1):
    if i*i < (N-1):
        if (N - 1)% i == 0:
            yakusuuu.append(i)
            yakusuuu.append((N-1)//i)
    elif i*i == (N-1):
        yakusuuu.append(i)
    else:
        break

for i in yakusuuu:
    if N % i == 1:
        ans += 1

#print(divisor)
#print(yakusuuu)

M = N

for K in divisor:
    #print(K)
    while M % K == 0:
        M = M//K

    

    if M == 1:
        ans += 1
        
    else:
        M =  M % K
        if M == 1:
            ans += 1 
    
    M = N
        




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

import numpy as np
N = int(input())
a = list(map(int,input().split()))
a = np.array(a)
a = np.sort(a)[::-1]
Flag = True
q = 0
add = a[0]
sum = 0
max = np.sum(a)-len(a)
n = a[0]*q+a[0]-1
while True:
    st = np.sum(n%a)
    if st == max:
        sum = st
        break
    ind = np.where(a - n%a == 1)[0]
    c = a[ind]
    n += np.prod(c)
print (sum)

### FIXED CODE ###

import numpy as np
N = int(input())
a = list(map(int,input().split()))
print (np.sum(a)-len(a))
### BUGGY CODE ###

import numpy as np


input_num = int(input()) + 1
result = 0
for a in range(1, input_num):
  for b in range(1, input_num):
    for c in range(1, input_num):
      result += np.gcd.reduce([a, b, c])
print(result)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*nums):
  return reduce(math.gcd, nums)


input_num = int(input()) + 1
result = 0
for a in range(1, input_num):
  for b in range(1, input_num):
    for c in range(1, input_num):
        result += gcd(a, b, c)

print(result)
### BUGGY CODE ###

from operator import mul
from functools import reduce

N,K = map(int,input().split())
A = list(map(int,input().split()))  
tempA = reduce(mul, A[0:K])

for i in range(N - K):
  mulA = tempA / A[i] * A[K+i]
  if tempA < mulA:
    print('Yes')
  else:
    print('No')
  tempA = mulA

  

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))  
for i in range(N - K):
  if A[i] < A[K+i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7

        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(set)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].add(b)
            adj[b].add(a)


        dp = [-1] * n
        done = [0] * n

        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    dp[s] = 0
                    return 0
                res *= rem * dfs(x, k - 2)
                res %= MOD
                rem -= 1
                if res == 0:
                    dp[s] = 0
                    return 0

            dp[s] = res
            return res

        dfs(0, k - 1)

        print((dp[0] * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

import fractions
N, M = map(int, input().split())

k = M // N + 1
ans = 1
for i in reversed(range(1, k+1)):
    if ans > i:
        break
    tmp = max(M - (N-1)*i, 1)
    ans = max(ans, fractions.gcd(i, tmp))

print(ans)


### FIXED CODE ###

import fractions
N, M = map(int, input().split())

k = M // N + 1
ans = 1
for i in reversed(range(1, k+1)):
    if ans > i:
        break
    tmp = max(M - (N-1)*i, 1)
    if tmp % i == 0:
        ans = max(ans, i)

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

n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(len(a)):
  for l in range(i+1,len(a)):
    ans += a[i]*a[l]
print(ans%(10**9+7))

### FIXED CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
cumsum = list(itertools.accumulate(a))
ans = 0
mod = 10**9+7
for i in range(1,n):
  ans += a[i]*cumsum[i-1]
print(ans%mod)
### BUGGY CODE ###

from functools import reduce
isstr=input()
n,m = [int(i) for i in isstr.split(' ')]
gate=[0]*m
for i in range(m):
    a,b=[int(i) for i in input().split(' ')]
    gate[i]=set([j for j in range(a,b+1)])
result=reduce(lambda x,y:x&y, gate)
count=0
for re in result:
  if re <=n:
    count+=1
print(count)
  	

### FIXED CODE ###

isstr=input()
n,m = [int(i) for i in isstr.split(' ')]
l=[0]*m
r=[0]*m
for i in range(m):
    l[i],r[i]=[int(i) for i in input().split(' ')]
result=min(r)-max(l)+1
result=result if result>0 else 0
print(result)
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
abc=[list(map(int,input().split())) for i in range(n)]
dp=[[[10**9]*401 for i in range(401)] for j in range(n+1)]
dp[0][0][0]=0
for i in range(1,n+1):
  for j in range(401):
    for k in range(401):
      if j-abc[i-1][0]>=0 and k-abc[i-1][1]>=0:
        dp[i][j][k]=min(dp[i-1][j][k],dp[i-1][j-abc[i-1][0]][k-abc[i-1][1]]+abc[i-1][2])
      else:
        dp[i][j][k]=dp[i-1][j][k]
ans=10**18
for j in range(1,401):
  for k in range(1,401):
    if dp[n][j][k]<10**9 and k*ma==j*mb:
      ans=min(ans,dp[n][j][k])
if ans==10**18:
  print(-1)
else: 
  print(ans)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
INF=10**17
dp=[[[INF]*(10*n+1) for i in range(10*n+1)] for j in range(n+1)]
dp[0][0][0]=0
ans=10**17
for i in range(n):
  a,b,c=map(int,input().split())
  for j in range(10*n+1):
    for k in range(10*n+1):
      if dp[i][j][k]!=INF:
        dp[i+1][j+a][k+b]=min(dp[i+1][j+a][k+b],dp[i][j][k]+c)
      dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k])
for i in range(1,10*n+1):
  for j in range(1,10*n+1):
    if i*mb==j*ma:
      ans=min(ans,dp[n][i][j])
if ans==INF:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
query = []
 
def func(string, t, f, c):
    if t == "1":
        new_str = ''.join(list(reversed(string)))
        return new_str
    else:
        if f == "1":
            return c + string
        else:
            return string + c
 
for i in range(0,q):
    query.append(input().split())
for i in query:
    if i[0] == "1":
        s = func(s,i[0],'','')
    else:
        s = func(s,i[0],i[1],i[2])
print(s)

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

import numpy as np
import sys
def resolve():
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    N = int(input())
    A = list(map(int,input().split()))
    ans = np.ones(N,dtype=int)
    for i in range(N):
        for j in range(N):
            if A[i] % A[j] == 0 and i != j:
                ans[i] = 0
                break
    print(sum(ans))
resolve()

### FIXED CODE ###

#写経
#https://atcoder.jp/contests/abc170/submissions/14363499
import sys

def resolve():
    it = map(int,sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    
    if N == 1:
        print(1)
        return
    ax = max(A) + 1
    dp = [0] * ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)
resolve()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
v = 1
m = int(1e+18)
for a in A:
    v *= a

if v > m:
    print(-1)
else:
    print(v)

### FIXED CODE ###

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

def f(A):
    for a in A:
        if a == 0:
            print(0)
            return
    v = 1
    for a in A:
        v *= a
        if v > int(1e+18):
            print(-1)
            return
    print(v)
    return

f(A)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for cost1, node1 in adj[node]:
            #if visited[node1] == True:
            #    continue
            heapq.heappush(h, [cost1, node1])
            
#print(d)
print(sum(d))
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###

N=int(input())
cnt=0
S=[input() for i in range(N)]
for i in range(N-1):
    for j in range(i+1,N):
        if sorted(S[i])==sorted(S[j]):
            cnt+=1
print(cnt)

### FIXED CODE ###

N=int(input())
cnt=0
dict={}
for i in range(N):
    s="".join(sorted(input()))
    if s in dict:
        cnt+=dict[s]
        dict[s]+=1
    else:
        dict[s]=1
print(cnt)
### BUGGY CODE ###

n, m = map(int, input().split())
cand_path = [tuple(map(int, input().split())) for _ in range(m)]

ans = 'IMPOSSIBLE'

for i in range(2, n):
  path = [1, n]
  path.insert(1, i)
  if len([True for x in zip(path, path[1:]) if x in cand_path])==2:
    ans = 'POSSIBLE'
    
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
all_cand = [tuple(map(int, input().split())) for _ in range(m)]

start_path_end = set([path[1] for path in all_cand if path[0]==1])
end_path_start = set([path[0] for path in all_cand if path[1]==n])

print('POSSIBLE' if start_path_end&end_path_start else 'IMPOSSIBLE')
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[-1] + A[i])
for i in range(M):
    B_sum.append(B_sum[-1] + B[i])

ans = 0
for i in range(N+1):
    for j in range(M, -1, -1):
        time = A_sum[i] + B_sum[j]
        if time > K:
            continue
        ans = max(i + j, ans)
        break
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A_sum = [0]
B_sum = [0]
for i in range(N):
    A_sum.append(A_sum[-1] + A[i])
for i in range(M):
    B_sum.append(B_sum[-1] + B[i])

ans = 0
j_max = M
for i in range(N+1):
    for j in range(j_max, -1, -1):
        time = A_sum[i] + B_sum[j]
        if time > K:
            continue
        j_max = j
        ans = max(i + j, ans)
        break
print(ans)
### BUGGY CODE ###

def solve(H, M, W, bombs):
    count_h = [0 for _ in range(H)]
    count_w = [0 for _ in range(W)]
    for b in bombs:
        count_h[b[0] - 1] += 1
        count_w[b[1] - 1] += 1
    max_h = max(count_h)
    max_w = max(count_w)
    points_h = [i for i, c in enumerate(count_h) if c == max_h]
    points_w = [i for i, c in enumerate(count_w) if c == max_w]
    ans = max_h + max_w
    if _find_cross_bomb(points_h, points_w, bombs):
        ans -= 1
    print(ans)


def _find_cross_bomb(points_h, points_w, bombs):
    for ph in points_h:
        for pw in points_w:
            if [ph + 1, pw + 1] in bombs:
                pass
            else:
                return False
    return True


if __name__ == "__main__":
    H, W, M = map(int, input().split())
    bombs = [list(map(int, input().split())) for i in range(M)]
    solve(H, M, W, bombs)


### FIXED CODE ###

import sys


def solve():
    readline = sys.stdin.readline
    H, W, M = map(int, readline().split())
    h = [0] * H
    w = [0] * W
    b = set()
    for _ in range(M):
        y, x = map(int, readline().split())
        x -= 1
        y -= 1
        h[y] += 1
        w[x] += 1
        b.add(y * W + x)
    h = sorted(zip(h, range(H)), reverse=True)
    ans = 0
    for i in range(W):
        x = w[i]
        for y, j in h:
            if x + y > ans:
                if j * W + i in b:
                    ans = x + y - 1
                else:
                    ans = x + y
                    break
            else:
                break
    print(ans)


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

#!/usr/bin/env python3

import itertools


UNDEF = 0


def mex(s):
    for i in itertools.count(1):
        if i not in s:
            return i


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF for _ in range(n - 1)]
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        while len(cur_cols) < num_adj:
            nc = mex(cur_cols)
            cur_cols.add(nc)
            new_cols.add(nc)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3

import itertools


UNDEF = 0


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF] * (n - 1)
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        for i in itertools.count(1):
            if len(cur_cols) + len(new_cols) >= num_adj:
                break
            elif i not in cur_cols:
                new_cols.add(i)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


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

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

ans=0
R=[0]*N
G=[0]*N
B=[0]*N

for i in range(N):
    if S[i]=='R':
        R[i]=1
    elif S[i]=='G':
        G[i]=1
    elif S[i]=='B':
        B[i]=1
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                if j-i != k-j:
                    ans+=1
print(ans)


### FIXED CODE ###

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

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


ans=r*g*b
dib=0
m=0

for i in range(N-2):
    m=(N+i)//2+1
    for j in range(i+1,m):
            dib=j-i
            if j+dib<=N-1:
                if S[i]!=S[j] and S[i]!=S[j+dib] and S[j]!=S[j+dib]:
                    ans=ans-1
            
print(ans)
### BUGGY CODE ###

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

median_idx = int(len(X_list) / 2) - 1

for idx, v in enumerate(X_list):
    X_copy = X_list.copy()
    X_copy.pop(idx)
    #median_idx = int((len(X_copy) + 1) / 2) - 1
    #print(median_idx)
    X_copy.sort()
    print(X_copy[median_idx])


### FIXED CODE ###

N = int(input())
X_list = list(map(int, input().split()))
X_list_copy = X_list.copy()
X_list_copy.sort()

median_idx = int(N / 2)
left_num = X_list_copy[median_idx - 1]
right_num = X_list_copy[median_idx]

for x in X_list:
    if x < right_num:
        print(right_num)
    else:
        print(left_num)
### BUGGY CODE ###

N = input()
Q = 0
for i in range(int(N)+1):
  P = []
  for j in range(len(str(i))):
    k= str(i)
    P.append(int(k[j]))
  if(sum(P)%3 == 0 and P[-1]%5 == 0):
      Q += 0
  elif(sum(P)%3 == 0):
      Q += 0
  elif(P[-1] == 0 or P[-1] == 5):
      Q += 0
  else:
      Q += i
print(Q)

### FIXED CODE ###

N = int(input())
Q = 0
for i in range(1,N+1):
  if(i%3 != 0 and i%5 != 0):
      Q += i
print(Q)