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

H, W, M = map(int, input().split())

hdic = {}
wdic = {}
hws = []

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
    else:
        hdic[h] = 1
    
    if w in wdic.keys():
        wdic[w] += 1
    else:
        wdic[w] = 1
    hws.append([h, w])

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

for k, v in hdic.items():
    if v == hmax:
        hs.append(k)

for k, v in wdic.items():
    if v == wmax:
        ws.append(k)

f = 1
for h in hs:
    for w in ws:
        if [h, w] not in hws:
            f = 0
            break
    if f == 0:
        break

print(hmax + wmax - f)


### FIXED CODE ###

H, W, M = map(int, input().split())

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(ws) < len(hs):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break
        
else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)
### BUGGY CODE ###

Ask = input()
puts = Ask.split()


A = int(puts[0])
B = int(puts[1])

for i in range(max(A,B)):
	C = abs(A-i)
	D = abs(B-i)
	if (C == D):
		print(i)
		Pos = True
		break
	else:
		Pos = False
	
if not Pos:
	print('IMPOSSIBLE')


### FIXED CODE ###

Ask = input()
puts = Ask.split()


A = int(puts[0])
B = int(puts[1])
Ans = 0

Pos = False

if (A == B):
	Pos = True
elif (A**2 - B**2) % (2*(A-B)) == 0:
	Pos= True
	Ans =  (A**2 - B**2) / (2*(A-B))
	
if not Pos:
	print('IMPOSSIBLE')
else:
	print(int(Ans))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
out = [0] * n
count = 0
out_str = ""
for i in range(n):
    out[a[i] - 1] = i + 1
        
for i in range(n):
    out_str = out_str + str(out[i]) + " "

print(out_str[:-1])


### FIXED CODE ###

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

import itertools
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from sys import exit

N = int(input())

matr = [tuple(map(int, input().split())) for _ in range(N)]
way = floyd_warshall(matr).astype(int)
if np.any(way < matr):
    print(-1)
    exit()

ans = 0
for a, b in itertools.combinations(range(N), 2):
    for c in set(range(N)) - {a, b}:
        if matr[a][b] == matr[a][c] + matr[c][b]:
            break
    else:
        ans += matr[a][b]
print(ans)


### FIXED CODE ###

import itertools
import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    matr = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype=np.int64)
    way = floyd_warshall(matr).astype(int)
    if np.any(way < matr):
        print(-1)
        exit()

    ans = 0
    for a, b in itertools.combinations(range(N), 2):
        eq = (matr[a, b] == (matr[a] + matr[:, b]))
        eq[a] = eq[b] = False
        if not np.any(eq):
            ans += matr[a, b]
    print(ans)


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

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

dp = [0] * 6
dp[0] = N
T = [A,B,C,D,E]
ans = 0
while dp[5] < N:
    for i in range(4, -1, -1):
        if dp[i] == 0:
            continue
        dp[i+1] += min(dp[i],T[i])
        dp[i] -= min(dp[i],T[i])
    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

dp = [0] * 6
dp[0] = N
T = [A,B,C,D,E]
ans = 0

ans = -(-N//min(T)) + 4
# while dp[5] < N:
#     for i in range(4, -1, -1):
#         if dp[i] == 0:
#             continue
#         dp[i+1] += min(dp[i],T[i])
#         dp[i] -= min(dp[i],T[i])
#     ans += 1
print(ans)
### BUGGY CODE ###

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

for i in range(q):
    a.sort()
    j = b[i][0]
    k = b[i][1]
    if j in a:
        for i in range(n):
            if a[i] <= j:
                if a[i] == j:
                    a[i] = k
            else:
                break
        print(sum(a))
    else:
        print(sum(a))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
q = int(input())
l = [list(map(int,input().split())) for i in range(q)]
b,c = [list(i) for i in zip(*l)]
x = collections.Counter(a)
y = sum(a)
for i in range(q):
    if b[i] in x:
        y -= x[b[i]] * b[i]
        y += x[b[i]] * c[i]
        x[c[i]] += x[b[i]]
        x[b[i]] = 0
    print(y)
### BUGGY CODE ###


import math
from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

k = int(input())
res = 0
for c in range(1,k+1):
    for b in range(1,k+1):
        for a in range(1,k+1):
            # res += gcd(a,b,c)
            gcd1 = math.gcd(a,b)
            gcd2 = math.gcd(gcd1,c)
            res += gcd2
print(res)

### FIXED CODE ###

import math
from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

k = int(input())
res = 0
for c in range(1,k+1):
    for b in range(1,k+1):
        gcd_cd = math.gcd(c,b)
        for a in range(1,k+1):
            # res += gcd(a,b,c)
            gcd_abc = math.gcd(a,gcd_cd)
            res += gcd_abc
print(res)
### BUGGY CODE ###

import numpy as np
n=int(input())
s=np.zeros((100001),dtype='int16')
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]

for i in range(n+1):
    s[i]=i
for i in range(1,12):
    for j in range(n+1):
        if a[i]<=j:
            if s[j]>s[j-a[i]]+1:
                s[j]=s[j-a[i]]+1
print(s[n])


### FIXED CODE ###

n=int(input())
s=[i for i in range(n+1)]
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(n+1):
    s[i]=i
for i in range(1,12):
    if a[i]<=n :
        k=a[i]
        for j in range(k,n+1):
            if s[j]>s[j-k]+1:
                s[j]=s[j-k]+1
print(s[n])
### BUGGY CODE ###

import numpy as np

N = int(input())
xyi = []
xi  = []
yi  = []
ans = 0
for i in range(N):
  xyi.append(list(map(int, input().split())))
  xi.append(xyi[i][0])
  yi.append(xyi[i][1])
  x = np.array(xi)
  y = np.array(yi)
  if i >0 :
    x_temp = np.abs(x[i] - x[:i])
    y_temp = np.abs(y[i] - y[:i])
    xy_temp = x_temp + y_temp
    temp = np.max(xy_temp)
    if temp > ans:
      ans = temp
  
  
print(ans)

### FIXED CODE ###

N = int(input())
z =[]
w = []
for i in range(N):
  x,y = map(int, input().split())
  z.append(x+y)
  w.append(x-y)
print(max(max(z)-min(z),max(w)-min(w)))
### BUGGY CODE ###

import itertools

max_range, sum_ = map(int, input().split())

count = 0
for x, y, z in itertools.combinations_with_replacement(range(max_range + 1), r=3):
    if x + y + z == sum_:
        len_set = len({x, y, z})
        if len_set == 1:
            count += 1
        elif len_set == 2:
            count += 3
        else:
            count += 6

print(count)


### FIXED CODE ###

max_range, sum_ = map(int, input().split())

count = 0
for x in range(0, min(max_range + 1, sum_ + 1)):
    for y in range(0, min(max_range + 1, sum_ - x + 1)):
        if sum_ - x - y <= max_range:
            count += 1

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

N = int(input())
S = input()
L = []
Ans = 0
for i in range(N):
  s = S[i]
  a = 0
  b = 0
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      K = ["R","G","B"]
      K.remove(s)
      if t == K[0]:
        a +=1
      else:
        b +=1
  Ans += a*b

for i in range(N):
  for j in range(i+1,N):
    s = S[i]
    t = S[j]
    k = 2*j-i
    if j < k <= N-1:
      u = S[k]
      if s != t and t != u and u != s:
        Ans -=1
print(Ans)

### FIXED CODE ###

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

L = [0,0,0]
for i in range(N):
    if S[i] == "R":
        L[0] +=1
    elif S[i] == "G":
        L[1] +=1
    else:
        L[2] +=1

Ans = L[0]*L[1]*L[2]

for i in range(N):
  s = S[i]
  n = min(N, (N+i)//2 + 1)
  for j in range(i+1,n):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)
### BUGGY CODE ###

import math
n = int(input())

# floor_root_n = math.ceil(math.sqrt(n))
# # a<=bとしてかんがえる
# s = 0
# if not math.sqrt(n).is_integer():
#     for i in range(1, floor_root_n+1):
#         print(i)
#         s += 2*(floor_root_n-i+1)
# else:
#     for i in range(1, floor_root_n):
#         print(i)
#         s += 2*(floor_root_n-i)+1
# print(s)
s = 0
a = 1
b = 1
while a*b < n:
    while a*b < n:
        b += 1
        s += 1
    a += 1
    b = 1
print(s)


### FIXED CODE ###

n = int(input())

s = 0
a = 1
b = 1
while a*b < n:
    while a*b < n and b <= a:
        if a == b:
            s += 1
        else:
            s += 2
        b += 1
    a += 1
    b = 1
print(s)
### BUGGY CODE ###

n , m , q = map(int, input().split())
table = [[0]*n for i in range(n)]

for i in range(m):
    l , r = map(int, input().split())
    l-=1
    r-=1
    table[l][r]+=1

table_sum = table.copy()

for i in range(n):
    for j in range(1,n):
        table_sum[i][j]=table_sum[i][j]+table_sum[i][j-1]

for i in range(q):
    l , r = map(int, input().split())
    l-=1
    r-=1
    ans=0
    for j in range(l,r+1):
        if l!=0:
            ans+=table_sum[j][r]-table_sum[j][l-1]
        else:
            ans+=table_sum[j][r]
    print(ans)


### FIXED CODE ###

n , m , q = map(int, input().split())
table = [[0]*n for i in range(n)]

for i in range(m):
    l , r = map(int, input().split())
    l-=1
    r-=1
    table[l][r]+=1

table_sum = table.copy()

for i in range(n):
    for j in range(1,n):
        table_sum[i][j]=table_sum[i][j]+table_sum[i][j-1]

for i in range(q):
    l , r = map(int, input().split())
    l-=1
    r-=1
    ans=0
    for j in range(l,r+1):
        if l!=0:
            ans+=table_sum[j][r]-table_sum[j][l-1]
        else:
            ans+=table_sum[j][r]
    print(ans)
### BUGGY CODE ###

x = int(input())
l = int(x/105)
u = int(x/100)+1
flag = False
for n in range(l, u):
    for a in range(0, u):
        for b in range(0, u):
            for c in range(0, u):
                for d in range(0, u):
                    for e in range(0, u):
                        for f in range(0, u):
                            if 100*a + 101*b + 102*c + 103*d + 104*e + 105*f == x:
                                #print(a,b,c,d,e,f)
                                flag = True
                                break
                            if flag == True: break
                        if flag == True: break
                    if flag == True: break
                if flag == True: break
            if flag == True: break
        if flag == True: break
    if flag == True: break

if flag:
    print('1')
else:
    print('0')

### FIXED CODE ###

x = int(input())
l = int(x/105)
u = int(x/100)+1
flag = False
for n in range(l, u):
    for a in range(0, u):
        for b in range(0, u-a):
            for c in range(0, u-a-b):
                for d in range(0, u-a-b-c):
                    for e in range(0, u-a-b-c-d):
                        for f in range(0, u-a-b-c-d-e):
                            if 100*a + 101*b + 102*c + 103*d + 104*e + 105*f == x:
                                #print(a,b,c,d,e,f)
                                flag = True
                                break
                            if flag == True: break
                        if flag == True: break
                    if flag == True: break
                if flag == True: break
            if flag == True: break
        if flag == True: break
    if flag == True: break

if flag:
    print('1')
else:
    print('0')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)

    dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        if dp[A[i]] != -1:
            ans.append(dp[A[i]])
        else:
            t = 0
            for k,v in c.items():
                if k == A[i]:
                    if v-1 >= 2:
                        t += combination(v-1, 2)
                else:
                    if v >= 2:
                        t += combination(v, 2)
            ans.append(t)
            dp[A[i]] = t
 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    from collections import Counter
    import math
    from functools import lru_cache

    @lru_cache(None)
    def combination(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
    c = Counter(A)
    
    ta = 0
    for k,v in c.items():
        if v >= 2:
            ta += combination(v, 2)
            
    # dp = [-1] * (N+1)
    ans = []
    for i in range(N):
        t = ta
        if c[A[i]] >= 2:
            t -= combination(c[A[i]], 2)
        if c[A[i]]-1 >= 2:
            t += combination(c[A[i]]-1, 2)
        
        ans.append(t)

 
    for i in ans:
        print(i)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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


def main():
    M = 2019
    s = input()

    x = 0
    dp = [0] * M
    for c in s:
        c = int(c)
        dp2 = [0] * M
        for j in range(M):
            dp2[(j*10 + c) % M] += dp[j]
        dp2[c] += 1
        dp = dp2
        x += dp[0]
    print(x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

M = 2019
dp = [0] * M
s = input()
x = 0
for c in s:
    c = int(c)
    dp2 = [0] * M
    for j in range(M):
        index = (j*10 + c) % M
        dp2[index] += dp[j]
    dp = dp2
    dp[c] += 1
    x += dp[0]
print(x)
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        if s == t:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % MOD
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD

print((dp[N][M] + 1) % MOD)


### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (M + 1) for _ in range(N + 1)]  # dp[s][t]

for i, s in enumerate(S, start=1):
    for j, t in enumerate(T, start=1):
        v = dp[i - 1][j] + dp[i][j - 1]
        if s == t:
            v += 1
        else:
            v -= dp[i - 1][j - 1]
        dp[i][j] = v % MOD

print((dp[-1][-1] + 1) % MOD)
### BUGGY CODE ###

N, T = map(int, input().split())
AB = []
for i in range(N):
    AB.append(tuple(map(int, input().split())))

AB.sort()

ans = 0
dp = [0] * T

for a, b in AB:
    ans = max(ans, dp[-1] + b)
    for j in range(T-1, -1, -1):
        if j >= a:
            dp[j] = max(dp[j], dp[j-a] + b)

print(ans)


### FIXED CODE ###

import numpy as np

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

AB.sort()

ans = 0
dp = [0] * T
dp = np.zeros(T, int)

for a, b in AB:
    ans = max(ans, dp[-1] + b)
    dp[a:] = np.maximum(dp[a:], dp[:-a] + b)
    # for j in reversed(range(a, T)):
    #     dp[j] = max(dp[j], dp[j-a] + b)

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

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

ans = -1*(10**18)
for si in range(N):
  x = si
  s = list()
  total = 0
  l = 0
  while(1):
    x = PList[x]-1
    s.append(CList[x])
    l += 1
    total += CList[x]
    if x == si:
      break
  t = 0
  for i in range(l):
    t += s[i]
    if i+1 > K:
      break
    now = t
    if total > 0:
      e = (K-i-1)//l
      now += total*e
    ans = max(ans, now)  
print(ans)
    

### FIXED CODE ###

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

ans = -1*(10**18)
for si in range(N):
  x = si
  s = list()
  total = 0
  l = 0
  while(1):
    x = PList[x]-1
    s.append(CList[x])
    l += 1
    total += CList[x]
    if x == si:
      break
  t = 0
  for i in range(l):
    t += s[i]
    if i+1 > K:
      break
    now = t
    if total > 0:
      e = (K-i-1)//l
      now += total*e
    ans = max(ans, now)  
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
for ii in r5000:
  player_in_this_game = set()
  rn = range(n)
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if m in player_in_this_game or teki - 1 in player_in_this_game:
        #自分または相手に既に試合が組まれている
        pass
      elif a[teki - 1][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki - 1].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki - 1) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1


### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                i = 1
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                W[D[(l,r)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()


### FIXED CODE ###

def examD():
    N = I()
    AB = [LI() for _ in range(N-1)]
    V = [[] for _ in range(N)]
    for a,b in AB:
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    ans = []
    root = 0
    #親とdfsの順序記録
    parent = [0] * (N)
    order = []
    stack = [root]
    while stack:
        x = stack.pop()
        order.append(x)
        for y in V[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            stack.append(y)
#    print(parent); print(order)
    #辺の色...子の色
    color = [-1]*(N)

    for i in order:
        NG = color[i]
        cur = 1
        for j in V[i]:
            if j == parent[i]:
                continue
            if cur==NG:
                cur +=1
            color[j] = cur
            cur +=1
#    print(color)
    append = ans.append
    for a,b in AB:
        if parent[a-1]==b-1:
            #子の色を塗る
            append(color[a-1])
        else:
            append(color[b-1])
    print(max(ans))
    for v in ans:
        print(v)

def examE():
    N, K = LI()

    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(set(a))
l = []
c = 0
for i in range(len(b)):
    l.append(a.count(b[i]))
    l = sorted(l)
if len(l) - k < 0:
    print(0)
else:
    for i in range(len(l)-k):
        c += l[i]
    print(c)

### FIXED CODE ###

import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
c = collections.Counter(a).values()
counter = sorted(list(c))
print(sum(counter[:len(counter)-k]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
INF = 10**10
n = int(input())
a = [int(_) - (i + 1) for i, _ in enumerate(input().split())]

grief = INF
for b in set(a):
    tmp = sum([abs(ai - b) for ai in a])
    if tmp < grief:
        bb = b
        grief = tmp

print(grief)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(_) - (i + 1) for i, _ in enumerate(input().split())]

# INF = 10**10
# grief = INF
# for b in set(a):
#     tmp = sum([abs(ai - b) for ai in a])
#     if tmp < grief:
#         bb = b
#         grief = tmp

# print(grief)  # running time limit error

a.sort()
med = a[len(a) // 2]
grief = sum([abs(ai - med) for ai in a])
print(grief)