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

def main():
    a,b,q = map(int,input().split())
    A = []
    B = []
    
    for _ in range(a):
        A.append(int(input()))
    
    for _ in range(b):
        B.append(int(input()))
    
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),0)
        if x >A[-1]:
            return (right,float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (left,right)
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(input())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        sl = dist(A,x,sl)
        sr = dist(A,x,sr)
        tl = dist(B,x,tl)
        tr = dist(B,x,tr)
        p1 = min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr))
        p2 = max(sl,tl)
        p3 = max(sr,tr)
        print(min(p1,p2,p3))

if __name__ == '__main__':
    main()
    
    
    



### FIXED CODE ###

import sys
readline = sys.stdin.readline


def main():
    a,b,q = map(int,readline().split())
    A = [int(readline()) for i in range(a)]
    B = [int(readline()) for i in range(b)]
    def search(A,x):
        left =0
        right = len(A)-1
        
        if x<A[0]:
            return (float('inf'),abs(x - A[left]))
        if x >A[-1]:
            return (abs(x - A[right]),float('inf'))
        
        while left != right-1:
            center = (left+right)//2
            
            if A[center] > x:
                right = center
            else:
                left = center
        
        return (abs(x - A[left]),abs(x - A[right]))
    
    
    def dist(A,x,lr):
        if lr == float('inf'):
            return float('inf')
        return abs(x - A[lr])
    
    for _ in range(q):
        x = int(readline())
        sl,sr = search(A,x)
        tl,tr = search(B,x)
        print(min(min(sl,sr)+min(tl,tr)+min(min(sl,sr),min(tl,tr)),max(sl,tl),max(sr,tr)))

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

import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()

    ans = INF
    for x0, x1 in itertools.combinations_with_replacement(x_coordinate, 2):
        for y0, y1 in itertools.combinations_with_replacement(y_coordinate, 2):
            cnt = len([(i, j) for i, j in xy if x0 <= i <= x1 and y0 <= j <= y1])
            if cnt >= K:
                ans = min((x1 - x0) * (y1 - y0), ans)

    print(ans)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import collections, itertools, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    xy = [LI() for _ in range(N)]

    # x, y全ての重複あり組み合わせに対して含まれる点の個数を算出する

    x_cnt = collections.Counter([i[0] for i in xy])
    x_coordinate = list(x_cnt.keys())
    x_coordinate.sort()
    # len_x_c = len(x_coordinate)
    y_cnt = collections.Counter([i[1] for i in xy])
    y_coordinate = list(y_cnt.keys())
    y_coordinate.sort()
    len_y_c = len(y_coordinate)

    ans = INF
    for xl, xh in itertools.combinations(x_coordinate, 2):
        # 4番目の辺の探索は、個数条件を満たしたら終了していよい
        for i in range(len_y_c - 1):
            yl = y_coordinate[i]
            for j in range(i + 1, len_y_c):
                yh = y_coordinate[j]
                cnt = len([(i, j) for i, j in xy if xl <= i <= xh and yl <= j <= yh])
                if cnt >= K:
                    ans = min((xh - xl) * (yh - yl), ans)
                    break

    print(ans)

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

s = int(input())

x1, y1, x2, y2, x3, y3 = 0, 0, 0, 0, 0, 0

while True:
    if s >= 10e9:
        for i in range(int(s**0.5), 0, -1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i
                y3 = s//i
                break
    else:
        for i in range(1, int(s**0.5) + 1):
            if s % i == 0 and i <= 10e9 and s / i <= 10e9:
                x2 = i - x1
                y3 = s//i
                break

    if x2 == 0 and y3 == 0:
        y2 = 1
        x3 += 1
        s += x3
        continue
    break

print(x1, y1, x2, y2, x3, y3)


### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

from fractions import*
n,*a=map(int,open(0).read().split())
r=range(n)
s=1
for i in r:s*=a[i]//gcd(s,a[i])
print(sum(s//a[i]for i in r)%(10**9+7))

### FIXED CODE ###

from fractions import*
from functools import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=reduce(lambda x,y:x//gcd(x,y)*y,a)%M
c=0
for i in a:
    c+=s*pow(i,M-2,M)
    c%=M
print(c)
### BUGGY CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.count = [1] * (n + 1)

    # find
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # union
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.count[y] += self.count[x]
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                self.count[x] += self.count[y]

    # size
    def size(self, x):
        return self.count[self.par[x]]

    # same
    def issame(self, x, y):
        return self.find(x) == self.find(y)

n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
b = [(j,i)for j in range(1,n+1) for i in range(j+1,n+1)]
U=UnionFind(n)
dis=[0]
cn=0
for i,j in reversed(a):
    if U.issame(i,j)==True:
        dis.append(cn)
    else:
        cn+=U.size(i)*U.size(j)
        dis.append(cn)
    U.union(i, j)
M=int(n*(n-1)/2)
for x in reversed(dis[:-1]):
    print(M-x)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.count = [1] * (n + 1)

    # find
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # union
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.count[y] += self.count[x]
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                self.count[x] += self.count[y]

    # size
    def size(self, x):
        return self.count[self.par[x]]

    # same
    def issame(self, x, y):
        return self.find(x) == self.find(y)

n,m=map(int,input().split())
a=[tuple(map(int,input().split())) for i in range(m)]
U=UnionFind(n)
dis=[0]
cn=0
for i,j in reversed(a):
    if U.issame(i,j)==True:
        dis.append(cn)
    else:
        cn+=U.size(i)*U.size(j)
        dis.append(cn)
    U.union(i, j)
M=int(n*(n-1)/2)
for x in reversed(dis[:-1]):
    print(M-x)
### BUGGY CODE ###

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

# 1からNの中間点より手前に、より多くのマスへの分岐を持っていれば勝ち
# 幅優先で、最短ルートを記録する。
from collections import deque
que=deque()

import copy

# [番号, 0からのルート, 親]
que.append([0,[],-1])
Nhalf=None
while que:
  node=que.popleft()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    # Nへの到達ルートの中間点
    route.append(v)
#    print(route)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
#    print(Nhalf,E[Nhalf],"remove:",NhalfNext)
#    print("bef:",E)
    E[Nhalf].remove(NhalfNext)
#    print("after:",E[Nhalf])
#    print(NhalfNext,E[NhalfNext],"remove:",Nhalf)
    E[NhalfNext].remove(Nhalf)
#    print("af:",E)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    que.append([child,newroute,v])

# この木でもう一回数え直す。行ける場所が(N-2)の半数以上であれば勝ち
stack=[]
# 自分、親
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
#  print("reached:",v)
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
#print(count)
if count>N-count:
  print("Fennec")
else:
  print("Snuke")

### FIXED CODE ###

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

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

FenWin=0
SunWin=0
for i in range(N):
  if F[i]<=S[i]:
    FenWin+=1
  else:
    SunWin+=1
print(("Snuke","Fennec")[FenWin>SunWin])
### BUGGY CODE ###

import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W:
                if S[nh][nw] == '.':
                    if visited[nh][nw] == False:
                        cnt[nh][nw] = cnt[h][w]
                        visited[nh][nw] = True
                        Q.append([nh,nw])
                    else:
                        if cnt[nh][nw] > cnt[h][w]:
                            cnt[nh][nw] = cnt[h][w]
                            Q.append([nh,nw])
                else:
                    for j in range(-2,3):
                        for k in range(-2,3):
                            nh = h + j
                            nw = w + k
                            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                                if cnt[nh][nw] > cnt[h][w]:
                                    cnt[nh][nw] = cnt[h][w] + 1
                                    visited[nh][nw] = True
                                    Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1
    S = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        c = cnt[h][w]
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if cnt[nh][nw] > c:
                    cnt[nh][nw] = c
                    Q.appendleft([nh,nw])
        nc = c + 1
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > nc:
                        cnt[nh][nw] = nc
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




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

import math
def multiplyList(myList) : 
    result = 1
    for x in myList: 
         result = result * x  
    return result 
n=int(input())
l1=list(map(int,input().split()))
a=multiplyList(l1)
if a>10**18:
  print("-1")
else:
  print(a)

### FIXED CODE ###


n=int(input())
l1=list(map(int,input().split()))
p=1
k=0
if 0 in l1:
  print("0")
  exit()
for i in range(n):
  p*=l1[i]
  if p>10**18:
    k=1
    break
if k==1:
  print("-1")
else:
  print(p)
### BUGGY CODE ###

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

ans = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
  for j in range(i+1,N):
    if (i+j)%2 :
      continue
    k = (i+j)//2
    if len(set([S[i],S[k],S[j]])) == 3:
      ans -= 1
      
print(ans)

### FIXED CODE ###

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

ans = S.count('R') * S.count('G') * S.count('B')
for i in range(N):
  for j in range(i+1,N):
    if (i+j)%2 :
      continue
    k = (i+j)//2
    if len(set([S[i],S[k],S[j]])) == 3:
      ans -= 1
      
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

s = list(s)

flg_reverse = False


def query_1():
    global flg_reverse
    if flg_reverse is True:
        flg_reverse = False
    else:
        flg_reverse = True



def query_2(s, a, b):
    global flg_reverse
    if flg_reverse is False:
        if a == 2:
            s.append(b)
        elif a == 1:
            s.insert(0, b)
    else:
        if a == 1:
            s.append(b)
        elif a == 2:
            s.insert(0, b)


for i in range(q):
    array = list(input().split())
    if len(array) == 1:
        query_1()
    else:
        query_2(s, int(array[1]), array[2])

if flg_reverse is False:
    for i in s:
        print(i, end='')
else:
    for i in range(len(s)-1, -1, -1):
        print(s[i], end='')





### FIXED CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())
flg = 1
for i in range(q):
    array = input().split(' ')
    if array[0] == '1':
        flg *= -1
    elif array[0] == '2':
        if array[1] == '1' and flg == 1 or array[1] == '2' and flg == -1:
            s.appendleft(array[2])
        else:
            s.append(array[2])

s = list(s)
if flg == -1:
    s = s[::-1]

s = ''.join(s)
print(s)
### BUGGY CODE ###

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

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,w=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]

dp=[float("inf")]*(10**5+1)
dp[0]=0
for i in range(n):
  for j in range(10**5,A[i][1]-1,-1):
    dp[j]=min(dp[j],dp[j-A[i][1]]+A[i][0])
ans=0
for v,e in enumerate(dp):
  if e<=w:
    ans=v
print(ans)
### BUGGY CODE ###

import sys
cnt = 1
while True:
    x = sys.stdin.readline().strip()
    if x == 0:
        break
    print("Case {}: {}".format(cnt,x))
    cnt += 1

### FIXED CODE ###

import sys
cnt = 1
while True:
    x = sys.stdin.readline().strip()
    if x == "0":
        break
    print("Case {}: {}".format(cnt,x))
    cnt += 1
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
 
#ab = [list(map(int, input().split())) for _ in range(M)]
#cd = [list(map(int, input().split())) for _ in range(K)]
 
lstab = [[] for _ in range(N)]
lstcd = [[] for _ in range(N)]

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

for _ in range(K):
    c, d = map(int, input().split())
    lstcd[c-1].append(d-1)
    lstcd[d-1].append(c-1)
    
groups = []
visiteds = [0] * N

for i in range(N):
    if visiteds[i] == 1: continue
    temp = [i]
    visited = [i]
    visiteds[i] = 1
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visiteds[y] == 1:continue
            temp.append(y)
            visited.append(y)
            visiteds[y] = 1
    groups.append(visited)
    if sum(visiteds) == N:break
 
ans = [0] * N
for grp in groups:
    setgrp = set(grp)
    for j in grp:
        ans[j] = len(setgrp - set(lstcd[j])) - 1 - len(lstab[j])
 
print(*ans)

### FIXED CODE ###

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

N, M, K = map(int, input().split())
 
lstab = [[] for _ in range(N)]

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

visited = [0] * N
cnt = 0

for i in range(N):
    if visited[i] != 0: continue
    temp = [i]
    cnt += 1
    visited[i] = cnt
 
    while temp:
        x = temp.pop()
        for y in lstab[x]:
            if visited[y] != 0:continue
            temp.append(y)
            visited[y] = cnt

numcd = [ 0 ] * N
for _ in range(K):
    c, d = map(int, input().split())
    if visited[c-1] == visited[d-1]:
        numcd[c-1] += 1
        numcd[d-1] += 1    
    
ans = [0] * N
cnt = Counter(visited)

for i in range(N):
    ans[i] = cnt[visited[i]] - 1 - len(lstab[i]) - numcd[i]
 
print(*ans)
### BUGGY CODE ###

import collections, sys
input = sys.stdin.readline

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = [None for i in range(n - 1)]
queue = collections.deque([[1, 0]])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[edge.index((min(num, prev), max(num, prev)))]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        temp = edge.index((a, b))
        if color[temp] != None:
            continue
        else:
            if count == col:
                color[temp] = count + 1
                count += 2
            else:
                color[temp] = count
                count += 1
            queue.append([i, num])
print(max(color))
for i in range(n - 1):
    print(color[i])

### FIXED CODE ###

import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
color = {}
queue = collections.deque([(1, 0)])
while queue:
    temp = queue.popleft()
    num = temp[0]
    prev = temp[1]
    if prev:
        col = color[(prev, num)]
    else:
        col = 0
    count = 1
    for i in graph[num]:
        a, b = min(i, num), max(i, num)
        if (a, b) in color.keys():
            continue
        else:
            if count == col:
                color[(a, b)] = count + 1
                count += 2
            else:
                color[(a, b)] = count
                count += 1
            queue.append((i, num))
print(max([len(graph[i]) for i in range(n + 1)]))
for i, j in edge:
    print(color[(i, j)])