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

import numpy
x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans1=[0]*(10**5+1)
for i in range(10**5+1):
    ans1[i]=(1 if i in q and (i+1)//2 in q else 0 )

ans=numpy.cumsum(ans1)
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])

### FIXED CODE ###

x=int(input())
n=10**5
import math
def eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q=eratosthenes(n)

ans=[0]*(10**5+1)
for i in range(10**5):
    ans[i+1]=ans[i]+(1 if i+1 in q and (i+1+1)//2 in q else 0 )
for i in range(x):
    l,r = map(int,input().split())	
    print(ans[r]-ans[l-1])
### BUGGY CODE ###

n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    nums = []
    for i in range(n):
        if i in hole_ids:
            nums.append(0)
            continue

        if i == 0:
            nums.append(1)
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            nums.append(nums[-1] + 1)
        else:
            nums.append(nums[-1] + nums[-2])
    return nums[-1]


print(solve(n, hole_ids) % X)


### FIXED CODE ###

n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    # nums = []
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            # nums.append(0)
            nums[i] = 0
            continue

        if i == 0:
            # nums.append(1)
            nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            # nums.append(nums[-1] + 1)
            nums[i] = nums[i-1] + 1
        else:
            # nums.append((nums[-1] % X + nums[-2] % X) % X)
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    if i == 0:
        ans += 1
    elif min(P[:i]) >= P[i]:
        ans += 1

print(ans)


### FIXED CODE ###

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

current_min = float("inf")
ans = 0

for i in range(N):
    if current_min >= P[i]:
        current_min = P[i]
        ans += 1

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

n = int(input())
edges = [[0 for _ in range(n)] for _ in range(n)]
mem = [[0 for _ in range(n)] for _ in range(n)]
dist = []

for i in range(n):
    edges[i][int(input())-1] = 1

def has_edge(edges, v, t, d):
    targets = [i for i, e in enumerate(edges[v]) if e != 0]
    for target in targets:
        if mem[v][target] == 0:
            mem[v][target] = 1
            if target == t:
                dist.append(d)
                return True
            else:
                return has_edge(edges, target, t, d+1)
    return False


print(min(dist)+1) if has_edge(edges, 0, 1, 0) else print(-1)

### FIXED CODE ###

n = int(input())
edges = {i: int(input())-1 for i in range(n)}


def push_buttom(v, goal):
    for i in range(n):
        v = edges[v]
        if v == goal:
            return i+1
    return -1


print(push_buttom(0, 1))
### BUGGY CODE ###

k,q = map(int,input().split())
d_array = list(map(int,input().split()))

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

for nxm in nxm_array:
    n, x, m = nxm
    d_mod_array = [d % m for d in d_array]
    d_sum = sum(d_mod_array)
    mod_total = x % m + d_sum * ((n-1) // k) + sum(d_mod_array[:(n-1)%k])
    reduce_total = mod_total // m

    zero_count = d_mod_array.count(0)
    zero_total = zero_count * ((n-1) // k) + d_mod_array[:(n-1)%k].count(0)
    ans = (n-1) - reduce_total - zero_total
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q = map(int,input().split())
d_array = list(map(int,input().split()))

ans_array = []
for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = 0
    d_part = 0
    zero_count = 0
    zero_part = 0
    part = (n-1) % k
    for i,d in enumerate(d_mod_array):
        d_sum += d
        if i < part:
            d_part += d
        if d == 0:
            zero_count += 1
            if i < part:
                zero_part += 1
    mod_total = x % m + d_sum * ((n-1) // k) + d_part
    reduce_total = mod_total // m

    zero_total = zero_count * ((n-1) // k) + zero_part
    ans = (n-1) - reduce_total - zero_total
    ans_array.append(str(ans))

print("\n".join(ans_array))
### BUGGY CODE ###

N, C = map(int, input().split())
imos = [0] * 100002
channel = [[0] * 100002 for i in range(C)]

for i in range(N):
    s, t, c = map(int, input().split())
    channel[c - 1][s] += 1
    channel[c - 1][t] -= 1

for i in range(C):
    for j in range(100001):
        channel[i][j + 1] += channel[i][j]

for i in range(C):
    for j in range(100001):
        if channel[i][j] == 0 and channel[i][j + 1] == 1:
            imos[j] += 1
        elif channel[i][j] == 1 and channel[i][j + 1] == 0:
            imos[j + 1] -= 1

for j in range(100001):
    imos[j + 1] += imos[j]

print(max(imos))


### FIXED CODE ###

N, C = map(int, input().split())
imos = [0] * 100002
channel = [[0] * 100002 for i in range(C)]

for i in range(N):
    s, t, c = map(int, input().split())
    channel[c - 1][s] += 1
    channel[c - 1][t] -= 1

for i in range(C):
    for j in range(100001):
        channel[i][j + 1] += channel[i][j]

for i in range(C):
    for j in range(100001):
        if channel[i][j] == 0 and channel[i][j + 1] == 1:
            imos[j] += 1
        elif channel[i][j] == 1 and channel[i][j + 1] == 0:
            imos[j + 1] -= 1

for j in range(100001):
    imos[j + 1] += imos[j]

print(max(imos))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
b = sorted(list(map(int, input().split())), reverse = True)
c = sorted(list(map(int, input().split())), reverse = True)
d = []
e = []
for m in range(x):
    for n in range(y):
        d.append(a[m]+b[n])
d.sort(reverse = True)
for m in range(z):
    for n in range(min(3000, len(d))):
        e.append(c[m]+d[n])
e.sort(reverse = True)
for n in range(k):
    print(e[n])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse = True)
b = sorted(list(map(int, input().split())), reverse = True)
c = sorted(list(map(int, input().split())), reverse = True)
d = []
e = []
for m in range(x):
    for n in range(y):
        d.append(a[m]+b[n])
d.sort(reverse = True)
for m in range(z):
    for n in range(min(3000, len(d))):
        e.append(c[m]+d[n])
e.sort(reverse = True)
for n in range(k):
    print(e[n])
### BUGGY CODE ###

command_num = int(input())
dict = []

for i in range(command_num):
    in_command, in_str = input().rstrip().split(" ")
    
    if in_command == "insert":
        dict.append(in_str)
    elif in_command == "find":
        if dict.count(in_str) > 0:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

command_num = int(input())
dict = set([])

for i in range(command_num):
    in_command, in_str = input().rstrip().split(" ")
    
    if in_command == "insert":
        dict.add(in_str)
    elif in_command == "find":
        if in_str in dict:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

import collections

N = int(input())

S_list = []

for i in range(N):
    s = input()
    S_list.append(s)

c = collections.Counter(S_list)
c_max = c.most_common()
max_num = c.most_common()[0][1]
ans_list = []
ans_list.append(c.most_common()[0][0])

for i in range(1, len(c_max)):
    if c.most_common()[i][1] != max_num:
        break
    else:
        ans_list.append(c.most_common()[i][0])

print(*sorted(ans_list), sep='\n')


### FIXED CODE ###

import collections

N = int(input())

S_list = []

for i in range(N):
    s = input()
    S_list.append(s)

c = collections.Counter(S_list)
c_max = c.most_common()
max_num = c.most_common()[0][1]
ans_list = []
ans_list.append(c.most_common()[0][0])

for i in range(1, len(c_max)):
    if c_max[i][1] != max_num:
        break
    else:
        ans_list.append(c_max[i][0])

print(*sorted(ans_list), sep='\n')
### BUGGY CODE ###

s=input()

stack=[]
for si in s:
    stack = stack + [si]
    if len(stack) >= 2 and stack[-1] != stack[-2]:
        del stack[-1]
        del stack[-1]
print(len(s)-len(stack))

### FIXED CODE ###

s=input()

stack=[]
for si in s:
    stack.append(si)
    if len(stack) >= 2 and stack[-1] != stack[-2]:
        del stack[-1]
        del stack[-1]
print(len(s)-len(stack))
### BUGGY CODE ###

import math
import bisect
import sys
input = sys.stdin.readline
q = int(input())
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

prime = set(eratosthenes(10**5))
like = []
for p in prime:
    if (p+1)//2 in prime:
        like.append(p)
like.sort()

for i in range(q):
    l, r = map(int, input().split())
    st = bisect.bisect_left(like, l)
    en = bisect.bisect_left(like, r)

    print(en-st)

    

### FIXED CODE ###

import math
import bisect
import sys
input = sys.stdin.readline
q = int(input())

def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False

prime = set([i for i, f in enumerate(sieve_of_erastosthenes(10**5)) if f])
like = []
for p in prime:
    if (p+1)//2 in prime:
        like.append(p)
like.sort()

for i in range(q):
    l, r = map(int, input().split())
    st = bisect.bisect_left(like, l)
    en = bisect.bisect_right(like, r)

    print(en-st)
### BUGGY CODE ###

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

WtoBcounter = 0
for i in range(N):
    if S[i] == "#":
        for j in range(i+1, N):
            if S[j] == ".":
                WtoBcounter += 1
        break

BtoWcounter = 0
for i in range(N-1, -1, -1):
    if S[i] == ".":
        for j in range(i-1, -1, -1):
            if S[j] == "#":
                BtoWcounter += 1

output = 0
if WtoBcounter < BtoWcounter:
    output = WtoBcounter
else:
    output = BtoWcounter

print(output)

### FIXED CODE ###

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

BtoW_stones_num = 0
for i in range(N):
    if S[i] == "#":
        BtoW_stones_num += 1

count = 0
brack_stone_num = 0
white_stone_num = 0
WtoB_stone_num = 0
for i in range(N-1, -1, -1):
    if S[i] == "#":
        if  white_stone_num == 0:
            brack_stone_num = 0
        else:
            brack_stone_num += 1
        if brack_stone_num > white_stone_num:
            WtoB_stone_num += white_stone_num
            brack_stone_num = 0
            white_stone_num = 0
    else:
        white_stone_num += 1
    
print(brack_stone_num + WtoB_stone_num)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
X,Y = 0,0
dp = [[0] * (N+1) for i in range(N+1)]
# dp[i][j] ans = dp[1][N]
for i in range(1,N+1):
    if N % 2 == 1:
        dp[i][i] = a[i-1]
    else:
        dp[i][i] = -a[i-1]
for i in range(N-1,0,-1):
    for j in range(1,N+1):
        if i >= j: continue
        if (j - i) % 2 != N % 2:
            dp[i][j] = max(a[i-1] + dp[i+1][j],a[j-1] + dp[i][j-1])
        else:
            dp[i][j] = min(-a[i-1] + dp[i+1][j],-a[j-1] + dp[i][j-1])
print(dp[1][N])

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
X,Y = 0,0
dp = [[0] * (N+1) for i in range(N+1)]
# dp[i][j] ans = dp[1][N]
for i in range(1,N+1):
    if N % 2 == 1:
        dp[i][i] = a[i-1]
    else:
        dp[i][i] = -a[i-1]
for i in range(N-1,0,-1):
    for j in range(1,N+1):
        if i >= j: continue
        if (j - i) % 2 != N % 2:
            dp[i][j] = max(a[i-1] + dp[i+1][j],a[j-1] + dp[i][j-1])
        else:
            dp[i][j] = min(-a[i-1] + dp[i+1][j],-a[j-1] + dp[i][j-1])
print(dp[1][N])
### BUGGY CODE ###

#!/usr/bin/env pypy3
def main():
    S = input()

    ans = 0
    len_S = len(S)
    for i in range(len_S):
        for j in range(i + 1, len_S + 1):
            res = int(S[i:j])
            if res % 2019 == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    S = input()[::-1]

    counts = [0] * 2019
    counts[0] = 1
    res, digit = 0, 1
    for i in S:
        res += int(i) * digit
        res %= 2019
        digit *= 10
        digit %= 2019
        counts[res] += 1

    ans = 0
    for i in counts:
        ans += i * (i - 1) // 2
    print(ans)


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

# -*- coding: utf-8 -*-
import re
# input
n, q = map(int, input().split())
#a = [0 for i in range(n)]
a = []
s = input()
for k in range(n):
    a.append(1) if s[k:k+2] == 'AC' else a.append(0)
# for m in re.finditer('AC', s):
#    a[m.start()] = 1
for i in range(q):
    l, r = map(int, input().split())
    print(sum(a[l-1:r-1]))

### FIXED CODE ###

# input
n, q = map(int, input().split())
a = [0 for i in range(n+1)]
s = input()
for i in range(n):
    a[i+1] = a[i] + (1 if s[i:i+2] == 'AC' else 0)
# for m in re.finditer('AC', s):
#    a[m.start()] = 1
for i in range(q):
    l, r = map(int, input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

import numpy as np
np.set_printoptions(suppress=True)
from collections import Counter
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

s = list(input())

l = len(s)
ans = 0

dp = np.zeros((3, l))

for i in range(l):
    dp[0][i] = int(s[i])
    dp[1][i] = (int(s[i]) * (10**(l-i-1))) % 2019

dp[2][l-1] = dp[0][l-1]

for i in range(l-2, -1, -1):
    c = i
    a = dp[1][i]
    b = dp[2][i+1]
    dp[2][i] = (dp[1][i] + dp[2][i+1]) % 2019

c = Counter(dp[2])
for i, j in c.items():
    if i == 0:
        ans += combinations_count(j+1, 2)
    elif j >= 2:
        ans += combinations_count(j, 2)

print(ans)

### FIXED CODE ###

s = input()[::-1]
l = len(s)
MOD = 2019
ans = 0
mods = [0] * 2019
mods[0] = 1
num = 0
cnt = 0
d = 1
for i in s:
    num += int(i) * d
    num %= MOD
    mods[num] += 1
    d *= 10
    d %= MOD

for j in mods:
    ans += int(j*(j-1)/2)

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

N = int(input())
S = []
for _ in range(N):
    S.append(input())

setS = set(S)
C = {s:S.count(s) for s in setS}
M = max(C.values())

R = [s for s in setS if C[s]==M]
R.sort()

for r in R:
    print(r)



### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())

import collections    
C = collections.Counter(S)
M = C.most_common()[0][1]
R = [c for c in C.keys() if C[c]==M]
R.sort()

for r in R:
    print(r)
### BUGGY CODE ###

N = int(input())

for h in range(1,3501):
    for n in range(h,3501):
        wd = 4*h*n - n*N - h*N
        wu = N*h*n
        if wd > 0 and wu % wd == 0:
            w = wu // wd
            print(h,n,w)
            exit()


### FIXED CODE ###

N = int(input())

for h in range(1,3501):
    for n in range(h,3501):
        wd = 4*h*n - n*N - h*N
        wu = N*h*n
        if wd > 0 and wu % wd == 0:
            w = wu // wd
            print(h,n,w)
            exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print(-1)
    exit()
srted.reverse()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

### FIXED CODE ###

from collections import deque
def tsort():
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    if len(l)!=P:
        print(-1)
        exit()
    return l
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
In=[0]*P
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
        In[A[i][j+1]]+=1
srted=tsort()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))
### BUGGY CODE ###

import collections
N, QQ = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
PX = [[int(_) for _ in input().split()] for _ in range(QQ)]
cd = collections.defaultdict
G = cd(set)
for ab in AB:
    a, b = ab
    G[a].add(b)
    G[b].add(a)
count = [0] * (N + 1)
for px in PX:
    p, x = px
    count[p] += x
ans = [0] * (N + 1)
visited = [False] * (N + 1)
visited[1] = 1
Q = [1]
while Q:
    q = Q.pop()
    for nq in G[q]:
        if not visited[nq]:
            visited[nq] = True
            Q += [nq]
            count[nq] += count[q]
print(*count[1:])


### FIXED CODE ###

import collections
N, QQ = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
PX = [[int(_) for _ in input().split()] for _ in range(QQ)]
cd = collections.defaultdict
G = cd(set)
for ab in AB:
    a, b = ab
    G[a].add(b)
    G[b].add(a)
count = [0] * (N + 1)
for px in PX:
    p, x = px
    count[p] += x
ans = [0] * (N + 1)
visited = [False] * (N + 1)
visited[1] = 1
Q = [1]
while Q:
    q = Q.pop()
    for nq in G[q]:
        if not visited[nq]:
            visited[nq] = True
            Q += [nq]
            count[nq] += count[q]
print(*count[1:])
### BUGGY CODE ###

n = input()
a_list = [int(a) for a in input().split(" ")]

a_len = len(a_list)
max = 10**9 + 7

sum = 0
for i in range(0, (a_len-1)):
  for j in range(i+1, a_len):
    sum += a_list[i] * a_list[j]

sum = sum % max
print(sum)



### FIXED CODE ###

n = input()
 
max = 10**9 + 7
 
a_list = [int(a) % max for a in input().split(" ")]
a_sum = sum(a_list)

total = 0
for i in range(0, len(a_list)-1):
    a_sum -= a_list[i]
    total += a_list[i] * a_sum
total = total % max
print(total)
### BUGGY CODE ###

N,P = map(int,input().split())
S =list(map(int,list(input())))

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1

else:
    data = [0] * P
    S = "".join(list(map(str,S)))
    for i in range(N):
        data[int(S[i:])%P] += 1
    #print(data)
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

print(ans)

### FIXED CODE ###

N,P = map(int,input().split())
S = str(input())

if P == 2 or P == 5:
    S = list(map(int,list(S)))
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1

else:
    data = [0] * P
    s = int(S)
    x = 1 ##10**iをPで割った数
    y = 0 ##S[i:N]をPで割った数
    for i in range(N):
        y += int(S[N-i-1]) * x
        y %= P
        data[y] += 1
        x *= 10
        x %= P
    #print(data)
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

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

from collections import deque
def main():
    n = int(input())
    ab = []
    colors = [[-1 for _ in range(n)] for _ in range(n)]
    visit = [-1 for _ in range(n)]
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    visit[0] = 0
    q = deque([0])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 +((d+1)==visit[s])
                colors[s][i] = visit[i] = d
                q.append(i)
    print(max([len(i) for i in tree]))
    for a, b in ab:
        print(colors[a-1][b-1])

if __name__=="__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    n = int(input())
    ab = []
    visit = [-1 for _ in range(n+1)]
    tree = [[] for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a].append(b)
        tree[b].append(a)
    visit[1]=0
    q = deque([1])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

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

from collections import deque

n = int(input())
nums = deque([])

for i in range(n):
  a = int(input())
  try:
    nums.remove(a)
  except ValueError:
    nums.append(a)

print(len(nums))



### FIXED CODE ###

import collections
ans = 0
n = int(input())
nums = [int(input()) for i in range(n)]
con = collections.Counter(nums)

for i in con.values():
  if i % 2 != 0:
    ans += 1
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)

children = [0] * N

num_turn = 10**100

for j in range(N): # 子供ごと

	if S[j] == 'R':
		pos_next = j + 1
		while S[pos_next] == 'R':
			pos_next += 1

		num_until_turn = pos_next - j
		num_after_turn = num_turn - num_until_turn

		if num_after_turn % 2 == 0:
			children[pos_next] += 1
		else:
			children[pos_next-1] += 1

	else:  # 'L'
		pos_next = j - 1
		while S[pos_next] == 'L':
			pos_next -= 1

		num_until_turn = pos_next - j
		num_after_turn = num_turn - num_until_turn

		if num_after_turn % 2 == 0:
			children[pos_next] += 1
		else:
			children[pos_next+1] += 1

print(*children)


### FIXED CODE ###

S = input()
N = len(S)

children = [0] * N

turn_position = list()

for i in range(N-1):
	if S[i]=='R' and S[i+1]=='L':
		turn_position.append(i)

for turn_i in range(len(turn_position) - 1):
	turn_pos = turn_position[turn_i]
	turn_pos_next = turn_position[turn_i + 1]

	children[turn_pos] += 1
	children[turn_pos+1] += 1

	for pos_i in range(turn_pos+2, turn_pos_next):
		if S[pos_i] == 'L':
			if (pos_i - turn_pos) % 2 == 0:
				children[turn_pos] += 1
			else:
				children[turn_pos+1] += 1
		else:
			if (turn_pos_next - pos_i) % 2 == 0:
				children[turn_pos_next] += 1
			else:
				children[turn_pos_next+1] += 1

turn_pos_first = turn_position[0]
for pos_i in range(0, turn_pos_first):
	if (turn_pos_first - pos_i) % 2 == 0:
		children[turn_pos_first] += 1
	else:
		children[turn_pos_first+1] += 1

turn_pos_last = turn_position[-1]
children[turn_pos_last] += 1
children[turn_pos_last+1] += 1
for pos_i in range(turn_pos_last+2, N):
	if (pos_i - turn_pos_last) % 2 == 0:
		children[turn_pos_last] += 1
	else:
		children[turn_pos_last+1] += 1

print(*children)