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

from itertools import islice


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [[[], []] for _ in range(city_count + 1)]

    for express_index in range(1, express_count + 1):
        l, r = map(int, input().split())
        for city in islice(city_list, 1, l + 1):
            city[0].append(express_index)
        for city in islice(city_list, r, None):
            city[1].append(express_index)

    for city in city_list:
        city[0] = frozenset(city[0])
        city[1] = frozenset(city[1])

    for _ in range(query_count):
        p, q = map(int, input().split())
        city_p = city_list[p][0]
        city_q = city_list[q][1]
        print(len(city_p & city_q))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from array import array
from itertools import accumulate, repeat, starmap
from operator import add, itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for city_index in range(2, city_count + 1):
        city_list[city_index] = array('L', starmap(
            add, zip(*(city_list[city_index + i] for i in (-1, 0)))))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[q][q] - city_list[p - 1][q])


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

from math import ceil

n = int(input())
l = list(map(int, input().split()))
l.sort()
# print(l)
ans = 0
for i in range(len(l)):
    for left in range(i+1, len(l)):
        right = left
        while right+1 < len(l) and l[right+1] < l[left] + l[i]:
            right += 1
        ans += right - left

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(len(l)):
    right = i+1
    for left in range(i+1, len(l)):
        while right+1 < len(l) and l[right+1] < l[left] + l[i]:
            right += 1
        ans += right - left
        if right == left:
            right += 1

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

N=int(input())
a=[int(i) for i in input().split()]

#print(a)
counter = [0 for i in range(10**9+3)]
#print(counter[a[N-1]])
#print(counter[6])
for i in range(N):
    counter[a[i]] += 1
ans = 0
for i in range(N):
    if counter[i] < i:
        ans += counter[i]
    else:
        ans += counter[i] - i
print(ans)
            
    

    

### FIXED CODE ###

N=int(input())
a=[int(i) for i in input().split()]

counter = [0]*(10**5+10)
ans = 0
for i in range(N):
#    print('a[i]=')
#    print(a[i])
    if a[i] < 10**5 + 3:
        counter[a[i]] += 1
#        print('hoge')
    else:
        ans += 1
#    print(ans)
for i in range(10**5+3):
    if counter[i] < i:
        ans += counter[i]
 #       print(counter[i])
    else:
        ans += counter[i] - i
 #       print(counter[i]-i)
#    print(ans) 
 
print(ans)
### BUGGY CODE ###

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

ans = 1
for x in range(n):
    ans *= a[x]


if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

ans = 1

a.sort(reverse=True)

if 0 not in a:
    for x in range(n):
        ans *= a[x]

        if ans > 10**18:
            ans = -1
            break
else:
    ans = 0

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

# input
N, M, K = map(int, input().split())

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Frends[a].append(b)
    Frends[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].append(d)
    Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        if i > f:
            continue

        t = -1
        s = set([i, f])
        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            sand = s&g
            if t < 0:
                if len(sand) > 0:
                    t = j
                    if sand == s:
                        break
                    elif i in sand:
                        g.add(f)
                    else:
                        g.add(i)

            elif len(sand) > 0:
                #   同一人物を含む友人グループを結合
                fg[t] = fg[t] | g
                fg.pop(j)
                fglen -= 1
            
            j += 1

        if t < 0:
            fg.append(s)

# 友人候補を抽出、カウント
cand = [0 for _ in range(N)]
for i in range(N):
    for g in fg:
        if i in g:
            cand[i] = len(g)-len(Frends[i])-len(set(Blocked[i])&g)-1
            break

# output
#print(fg)
print(" ".join(map(str, cand)))


### FIXED CODE ###

# input
N, M, K = map(int, input().split())

Friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friends[a].add(b)
    Friends[b].add(a)

Blocked = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].add(d)
    Blocked[d].add(c)

# process
# 友人グループを作成
checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))

# output
print(" ".join(map(str, ans)))
### BUGGY CODE ###

import sys

i_f = sys.stdin

n = int(i_f.readline())

P = [list(map(int, i_f.readline().split())) for _ in range(n)]

q = int(i_f.readline())

for l in i_f:
    sx, tx, sy, ty = map(int, l.split())
    for i, p in enumerate(P):
        x, y = p
        if sx <= x <= tx and sy <= y <= ty:
            print(i)
    print('')

### FIXED CODE ###

import sys, math
from operator import itemgetter
from bisect import bisect_left, bisect_right

f_i = sys.stdin

def main():
    n = int(f_i.readline())
    
    lx = []
    ly = []
    li = []
    for i in range(n):
        x, y = map(int, f_i.readline().split())
        lx.append(x)
        ly.append(y)
        li.append(i)

    x_width = max(lx) - min(lx)
    y_width = max(ly) - min(ly)
    if x_width > y_width:
        P = list(zip(lx, ly, li))
    else:
        P = list(zip(ly, lx, li))
    P.sort()

    interval = int(math.sqrt(n))

    low = [v1 for v1, v2, i in P[::interval]]
    high = [v1 for v1, v2, i in P[interval - 1::interval]] + [float('inf')]

    S = []
    v2_sec_list = []
    for i in range(0, n, interval):
        si = P[i:i + interval]
        si.sort(key=itemgetter(1))
        v2_s = [p[1] for p in si]
        v2_sec_list.append(v2_s)
        S.append(si)

    A = []

    q = f_i.readline()

    for l in f_i:
        sx, tx, sy, ty = map(int, l.split())
        a = []
        if x_width > y_width:
            for i in range(bisect_left(high, sx), bisect_right(low, tx)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sy), bisect_right(k, ty)):
                    if sx <= v[j][0] <= tx:
                        a.append(v[j][2])
        else:
            for i in range(bisect_left(high, sy), bisect_right(low, ty)):
                v = S[i]
                k = v2_sec_list[i]
                for j in range(bisect_left(k, sx), bisect_right(k, tx)):
                    if sy <= v[j][0] <= ty:
                        a.append(v[j][2])
        
        if a:
            a.sort()
            A.extend(a)
        A.append('')

    print('\n'.join(map(str, A)))

main()
### BUGGY CODE ###

def kitaichi(x):
    return x * (x+1) / (2 * x)

def main():
    n, k = map(int, input().split())
    inlis = list(map(int, input().split()))
    kitalis = list(map(kitaichi, inlis))
    ans = 0
    for i in range(len(kitalis)-k+1):
        if ans < sum(kitalis[i:i+k]):
            ans = sum(kitalis[i:i+k])
            
    print(ans)



    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def kitaichi(x):
    return x * (x+1) / (2 * x)

def main():
    n, k = map(int, input().split())
    inlis = tuple(map(int, input().split()))
    kitalis = list(map(kitaichi, inlis))
    kitadic = {}
    kitadic[0] = kitalis[0] 
    for i in range(1, n):
        kitadic[i] = kitadic[i-1] + kitalis[i]
       
    tmp = 0
    if n == k:
        print(kitadic[n-1])
    else:
        for i in range(n - k):
            atai = kitadic[i+k] - kitadic[i]
            if tmp < atai:
                tmp = atai
        print(tmp)
        exit()



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

from itertools import permutations as pm

def main():
    n = int(input())
    s = input()

    red = [0 for i in range(n+1)]
    green = [0 for i in range(n+1)]
    blue = [0 for i in range(n+1)]

    for i in range(2,n+1):
        if s[i-2]=='R':
            red[i] = red[i-1] + 1
        else:
            red[i] = red[i-1]
        if s[i-2]=='G':
            green[i] = green[i-1] + 1
        else:
            green[i] = green[i-1]
        if s[i-2]=='B':
            blue[i] = blue[i-1] + 1
        else:
            blue[i] = blue[i-1]
    # red[n] = red[n-1]
    # green[n] = green[n-1]
    # blue[n] = blue[n-1]

    # print(red)
    # print(blue)
    # print(green)


    ans = 0
    for i in range(1,n+1):
        for j in range(i+2,n+1):

            for a,b,c in pm("RGB"):
                if s[i-1]==a and s[j-1]==c:
                    if b =="R":
                        ans += red[j] - red[i+1]
                    elif b=="G":
                        ans += green[j] - green[i+1]
                    elif b == "B":
                        ans += blue[j] - blue[i+1]
                    
                    if (j-i)%2==0 and s[(j-i)//2+i-1] == b:
                        ans -= 1
                    # print(i,j,b,ans)
    print(ans)

if __name__== "__main__":
    main()

### FIXED CODE ###

from itertools import permutations as pm

def main():
    n = int(input())
    s = input()

    red = [0 for i in range(n+1)]
    green = [0 for i in range(n+1)]
    blue = [0 for i in range(n+1)]

    for i in range(2,n+1):
        if s[i-2]=='R':
            red[i] = red[i-1] + 1
        else:
            red[i] = red[i-1]
        if s[i-2]=='G':
            green[i] = green[i-1] + 1
        else:
            green[i] = green[i-1]
        if s[i-2]=='B':
            blue[i] = blue[i-1] + 1
        else:
            blue[i] = blue[i-1]
    # red[n] = red[n-1]
    # green[n] = green[n-1]
    # blue[n] = blue[n-1]

    # print(red)
    # print(blue)
    # print(green)


    ans = 0
    for i in range(1,n+1):
        for j in range(i+2,n+1):

            if s[i-1]+s[j-1] == "RB" or s[i-1]+s[j-1] =="BR":
                ans += green[j] - green[i+1]
                if (j-i)%2==0 and s[(j-i)//2+i-1] == "G":
                    ans -= 1
            elif s[i-1]+s[j-1] == "RG" or s[i-1]+s[j-1] =="GR":
                ans += blue[j] - blue[i+1]
                if (j-i)%2==0 and s[(j-i)//2+i-1] == "B":
                    ans -= 1
            elif s[i-1]+s[j-1] == "BG" or s[i-1]+s[j-1] =="GB":
                ans += red[j] - red[i+1]
                if (j-i)%2==0 and s[(j-i)//2+i-1] == "R":
                    ans -= 1

    print(ans)

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

A,B,N=map(int,input().split())
print(max([int(A*x/B)-A*int(x/B) for x in range(1,N+1)]))

### FIXED CODE ###

A,B,N=map(int,input().split())
def f(x):
  return int(A*x/B)-A*int(x/B)

print(f(min(N,B-1)))
### BUGGY CODE ###

from collections import deque
import sys

N = int(input())

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

q = deque([])

q.append([b,[]])

while len(q) > 0:

    now = q.popleft()

    nb = now[0]
    nc = now[1]

    for i in range(len(nb)):

        if (i+1) == nb[i]:

            nex = nb.copy()
            nec = nc.copy()
            nec.append(nex[i])
            del nex[i]

            if len(nex) == 0:
                nec.reverse()
                print (" ".join(map(str,nec)))
                sys.exit()

            q.append([nex,nec])

print (-1)

            


### FIXED CODE ###

from collections import deque
import sys

N = int(input())

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

q = deque([])

q.append([b,[]])

dic = {}

while len(q) > 0:

    now = q.pop()

    nb = now[0]
    nc = now[1]

    for i in range(len(nb)):

        i = len(nb) - i - 1

        if (i+1) == nb[i]:

            nex = []
            nec = []
            for j in range(len(nb)):
                if j != i:
                    nex.append(nb[j])
            for j in range(len(nc)):
                nec.append(nc[j])
            
            nec.append(nb[i])
            

            s = " ".join(map(str,nex))
            if s in dic:
                continue
            dic[s] = 1

            if len(nex) == 0:
                nec.reverse()
                print (" ".join(map(str,nec)))
                sys.exit()

            q.append([nex,nec])
            break

print (-1)
### BUGGY CODE ###

#ALDS1_4-D Allocation
from collections import deque

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.popleft()
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:return False
    return True
    
n,k = input().split()
w = []
for i in range(int(n)):
    w.append(int(input()))

p = max(w)

while(1):
    x=deque(w)
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
### BUGGY CODE ###

class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

import sys
input = sys.stdin.readline
from collections import defaultdict
n,q = map(int,input().split())
a = list(map(int,input().split()))
lr = [list(map(int,input().split())) for i in range(q)]
ans = [0]*q
for i in range(q):
  lr[i].append(i)
lr.sort(key = lambda x:x[1])
bit = Bit(n+2)
dc = defaultdict(int)
cnt = 0
for L,R,p in lr:
  L -= 1
  for i in range(cnt,R):
    if dc[a[i]]:
      l = dc[a[i]]-1
      r = i
      bit.add(l+2,1)
      bit.add(r+2,-1)
    else:
      bit.add(1,1)
      bit.add(i+2,-1)
    dc[a[i]] = i+1
  ans[p] = bit.sum(L+1)
  cnt = R
for i in ans:
  print(i)

### FIXED CODE ###

class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

  def add(self,i,x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i

import sys
input = sys.stdin.readline
from collections import defaultdict
n,q = map(int,input().split())
a = list(map(int,input().split()))
lr = [tuple(map(int,input().split()))+(i,) for i in range(q)]
ans = [0]*q
lr.sort(key = lambda x:x[1])
bit = Bit(n+2)
dc = defaultdict(int)
cnt = 0
for L,R,p in lr:
  L -= 1
  for i in range(cnt,R):
    if dc[a[i]]:
      l = dc[a[i]]-1
      r = i
      bit.add(l+2,1)
      bit.add(r+2,-1)
    else:
      bit.add(1,1)
      bit.add(i+2,-1)
    dc[a[i]] = i+1
  ans[p] = bit.sum(L+1)
  cnt = R
print(*ans,sep="\n")
### BUGGY CODE ###

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

### FIXED CODE ###

k,s=map(int,input().split())
cnt=0
for i in range(k+1):
  if i>s:
    continue
  for j in range(k+1):
    if i+j>s:
      continue
    l=s-i-j
    if 0<=l<=k:
      cnt+=1
print(cnt)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353
dp = [[0]*(S+1) for _ in range(N+1)]
def main():
  dp[0][0] = 1
  for i in range(1, N+1):
    for j in range(0, S+1):
      dp[i][j] += 2*dp[i-1][j]
      dp[i][j] %= MOD
      if j-A[i-1] >= 0:
        dp[i][j] += dp[i-1][j-A[i-1]]
        dp[i][j] %= MOD
  print(dp[N][S])

if __name__ == "__main__":
  main()


### FIXED CODE ###

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

def main():
  dp = [0]*(S+1)
  dp[0] = 1
  for i in range(1, N+1):
    p = [0]*(S+1)
    dp, p = p, dp
    for j in range(0, S+1):
      dp[j] += 2*p[j]
      dp[j] %= MOD
      if j-A[i-1] >= 0:
        dp[j] += p[j-A[i-1]]
        dp[j] %= MOD
  print(dp[S])

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

K,S=input().split()
L=0
for i in range(0,int(K)+1):
    X=i
    for j in range(0,int(K)+1):
        Y=j
        Z=int(S)-(X+Y)
        if 0<=Z<=int(K):
            L=L+1
        
print(L)        
        

### FIXED CODE ###

K,S=input().split()
k=int(K)
s=int(S)
L=0
for X in range(0,k+1):
    for Y in range(0,k+1):
        Z=s-(X+Y)
        if 0<=Z<=k:
            L+=1
        
print(L)
### BUGGY CODE ###

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
  
dp = [0] * (W+1)

for i in range(n):
  for j in range(W, w[i]-1, -1):
    dp[j] = max(dp[j], dp[j-w[i]]+v[i])
    
print(dp[W])

### FIXED CODE ###

import numpy as np

n, W = map(int, input().split())
w = []
v = []
for i in range(n):
  w_, v_ = map(int, input().split())
  w.append(w_)
  v.append(v_)
  
dp = np.zeros(W+1, dtype=np.int64)
for i in range(n):
  dp[w[i]:] = np.maximum(dp[:-w[i]]+v[i], dp[w[i]:])
print(dp[W])
### 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())) 

c = [0] * N

for i in range(N-1):
    c[A[i]-1] = c[A[i]-1] + 1
   
for j in c:
    print(j)
### BUGGY CODE ###

from dataclasses import dataclass
from collections import deque


@dataclass
class Query:
    now: int
    prev: int
    cost: int


N, M = map(int, input().split())
E = [[] for _ in range(N + 1)]

for e in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

res = [-1 for _ in range(N + 1)]
cost = [float('inf') for _ in range(N + 1)]
cost[1] = 0

queue = deque()

for next in E[1]:
    queue.append(Query(next, 1, 1))

while len(queue):
    q = queue.popleft()
    if cost[q.now] > q.cost:
        res[q.now] = q.prev
        cost[q.now] = q.cost

    for next in E[q.now]:
        if cost[next] > q.cost + 1:
            queue.append(Query(next, q.now, q.cost + 1))

for r in res[2:]:
    if r == -1:
        print('No')
        exit()

print('Yes')
for r in res[2:]:
    print(r)


### FIXED CODE ###

from dataclasses import dataclass
from collections import deque


@dataclass
class Query:
    now: int
    prev: int
    cost: int


N, M = map(int, input().split())
E = [[] for _ in range(N + 1)]

for e in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

res = [-1 for _ in range(N + 1)]
cost = [float('inf') for _ in range(N + 1)]
cost[1] = 0

queue = deque()

for next in E[1]:
    queue.append(Query(next, 1, 1))

while len(queue):
    q = queue.popleft()
    if cost[q.now] > q.cost:
        res[q.now] = q.prev
        cost[q.now] = q.cost

        for next in E[q.now]:
            if cost[next] > q.cost + 1:
                queue.append(Query(next, q.now, q.cost + 1))

for r in res[2:]:
    if r == -1:
        print('No')
        exit()

print('Yes')
for r in res[2:]:
    print(r)
### BUGGY CODE ###

n, m = map(int, input().split())
A = [int(input()) for i in range(m)]
dp = [0] * (n + 1)
dp[0] = 1
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1

for i in range(2, n+1):
  if i in A:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9 + 7)
print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
A = set([int(input()) for i in range(m)])
dp = [0] * (n + 1)
dp[0] = 1
if 1 in A:
  dp[1] = 0
else:
  dp[1] = 1

for i in range(2, n+1):
  if i in A:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9 + 7)
print(dp[n])
### BUGGY CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(lambda x: int(x) % mod, input().split()))

out = 0
for i in range(n - 1):
    for j in range(n - i - 1):
        k = i + j + 1
        # print(A[i], A[k])
        out += (A[i] * A[k])
        out %= mod
print(out)

### FIXED CODE ###

mod = 10**9 + 7
n = int(input())
A = list(map(lambda x: int(x) % mod, input().split()))

# out = 0
# for i in range(n - 1):
#     for j in range(n - i - 1):
#         k = i + j + 1
#         # print(A[i], A[k])
#         out += (A[i] * A[k])
#         out %= mod
B = A[1:n]
B_s = 0
for i in range(n - 1):
    B_s += B[i] % mod

out = 0
for i in range(n - 1):
    out += A[i] * B_s
    out %= mod
    B_s -= A[i + 1]
    B_s %= mod
    if B_s < 0:
        B_s += mod

print(out)
### BUGGY CODE ###

import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        for tsugi in G[ima]:
            t = 1
            if V[tsugi] == 0:
                V[tsugi] = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        t = 1
        for tsugi in G[ima]:
            if V[tsugi] == 0:
                V[tsugi] = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

if __name__ == '__main__':
    main()