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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]


def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                # A[ny][nx] = "#"
                que.append((ny, nx))
 
                ans = max(ans, d[ny][nx])     
#    print(*d, sep="\n")
    return ans


if __name__ == "__main__":
    print(bfs())

    


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]


def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                # A[ny][nx] = "#"
                que.append((ny, nx))
 
                ans = max(ans, d[ny][nx])     
#    print(*d, sep="\n")
    return ans


if __name__ == "__main__":
    print(bfs())
### BUGGY CODE ###

def f_pond_skater(INF=float('inf')):
    from fractions import Fraction
    from math import ceil
    from collections import deque
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    def is_inside(row, col):
        return (0 <= row < H) and (0 <= col < W)

    # dist[row][col][dir]: スタートから出発してマス (row, col) で
    # 方向 dir を向くまでに要する最小コスト (3 次元配列を 1 次元配列にしている)
    dist = [INF] * (H * W * 4)
    dr, dc = (0, -1, 0, 1), (-1, 0, 1, 0)  # '0123' と '左上右下' を対応

    def to_id(row, col, direction):
        return (row * W + col) * 4 + direction

    queue = deque([(0, start_row, start_col, 0)])
    while queue:
        cost, row, col, direction = queue.pop()
        current_id = to_id(row, col, direction)
        dist[current_id] = cost

        # 1マス直進する
        nr, nc = row + dr[direction], col + dc[direction]
        move_id = to_id(nr, nc, direction)
        if (is_inside(nr, nc) and Grid[nr][nc] == '.' and
                dist[move_id] > cost + Fraction(1, K)):
            queue.appendleft((cost + Fraction(1, K), nr, nc, direction))

        # 向きを 90 度変える
        for i in (1, 3):
            rot_id = to_id(row, col, (direction + i) % 4)
            new_cost = ceil(float(cost))
            if dist[rot_id] > new_cost:
                queue.appendleft((new_cost, row, col, (direction + i) % 4))

    ans = min(dist[to_id(target_row, target_col, d)] for d in range(4))
    return ceil(float(ans)) if ans != float('inf') else -1

print(f_pond_skater())

### FIXED CODE ###

def f_pond_skater():
    from heapq import heappush, heappop
    H, W, K = [int(i) for i in input().split()]
    start_row, start_col, target_row, target_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    heap = []
    dist = [[float('inf')] * W for _ in range(H)]
    dist[start_row][start_col] = 0

    diff = ((0, 1), (1, 0), (0, -1), (-1, 0))
    heappush(heap, (0, start_row, start_col))
    while heap:
        cost, row, col = heappop(heap)
        cost_next = cost + 1

        if row == target_row and col == target_col:
            return cost

        for dr, dc in diff:
            nr, nc = row, col
            for _ in range(K):
                nr += dr
                nc += dc
                if not (0 <= nr < H and 0 <= nc < W) or Grid[nr][nc] == '@':
                    break
                if dist[nr][nc] > cost_next:
                    dist[nr][nc] = cost_next
                    heappush(heap, (cost_next, nr, nc))
                elif dist[nr][nc] == cost_next:
                    continue
                else:
                    break
    return -1

print(f_pond_skater())
### BUGGY CODE ###

# ABC151 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
        ret=-1
        for i in range(h):
            for j in range(w):
                ret=max(visited[i][j],ret)
    return ret
h,w=nm()
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            continue
        sy,sx=i,j
        visited = [[-1]*w for i in range(h)]
        t=bfs(sy,sx)
        ans=max(t,ans)
print(ans)


### FIXED CODE ###

# ABC151 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
    ret=-1
    for i in range(h):
        for j in range(w):
            ret=max(visited[i][j],ret)
    return ret
h,w=nm()
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            continue
        sy,sx=i,j
        visited = [[-1]*w for i in range(h)]
        t=bfs(sy,sx)
        ans=max(t,ans)
print(ans)
### BUGGY CODE ###

from collections import deque
s=deque(input())
q=int(input())
for i in range(q):
    query=input().split()
    if query[0] == "1":
        s.reverse()
    elif query[1] == "1":
        s.appendleft(query[2])
    else:
        s.append(query[2])
print("".join(s))


### FIXED CODE ###

from collections import deque
s=deque(input())
q=int(input())
flag = 2

for i in range(q):
    query=input().split()
    if query[0] == "1":
        flag = 3 - flag
    elif int(query[1]) - flag :
         s.appendleft(query[2])
    else:
        s.append(query[2])

if flag-2:
    s.reverse()

print("".join(s))
### BUGGY CODE ###

N = int(input())
S = list(input())
l = []
for i in range(N-2) :
    for j in range(i+1,N-1) :
        for k in range(j+1,N) :
            x = int(str(S[i]) + str(S[j]) + str(S[k]))
            l.append(x)

print(len(set(l)))

### FIXED CODE ###

N = int(input())
S = list(input())
ans = 0
for x in range(1000) :
    X = list(str(x).zfill(3))
    i = 0
    j = 0
    if X[0] in S[:N-2] :
        i = S.index(X[0])
    else :
        continue
    if X[1] in S[i+1:N-1] :
        j = S[i+1:N-1].index(X[1])+i+1
    else :
        continue
    if X[2] in S[j+1:N] :
        ans += 1
                        
print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N):
    if (N - i) % i == 0:
        if (N - i) // i <= i:
            break
        ans += ((N - i) // i)
    

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N):
    if (N - i) // i + 1 <= i:
        break
    if (N - i) % i == 0:
        if (N - i) // i <= i:
            break
        ans += ((N - i) // i)

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

import numpy as np
n,m,k = (int(x) for x in input().split())
a =np.array([int(x) for x in input().split()])
b =np.array([int(x) for x in input().split()])

count = 0
for i in range(n+1):
    for j in range(m+1):
        if np.sum(a[:i])+np.sum(b[:j]) > k:
            break
        if i+j>count:
            count = i+j
print(count)

### FIXED CODE ###

n,m,k = (int(x) for x in input().split())
y = 0
a = [0]
for x in input().split():
    y += int(x)
    a.append(y)
y = 0
b = [0]
for x in input().split():
    y += int(x)
    b.append(y)
    
ans = 0
j = m
for i in range(n+1):
    if a[i]>k:
        break
    while j >= 0:
        if a[i]+b[j]<=k:
            ans = max(ans,i+j)
            break
        j -= 1
print(ans)
### BUGGY CODE ###

from queue import Queue

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
#%%
q = Queue()

dist = [[10**5]*W for _ in range(H)]

dx = [0,1]
dy = [1,0]
c = 0
f = 0
if S[0][0]=='#':
    c = 1
    f = 1
q.put([c,f,0,0])
while not(q.empty()):
    c,f,x,y = q.get()
    for i in range(2):
        nc = c
        nx = x+dx[i]
        ny = y+dy[i]
        if nx>=H or ny>=W:
            continue
        
        if f==0 and (S[nx][ny]=='#'):
            nc = c+1
        
        if nc < dist[nx][ny]: 
            dist[nx][ny] = nc
            nf = S[nx][ny]=='#'
            q.put([nc,nf,nx,ny])
        
print(dist[H-1][W-1])
        
    

### FIXED CODE ###

from queue import Queue

H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
#%%
q = Queue()

dist = [[10**5]*W for _ in range(H)]

dx = [0,1]
dy = [1,0]
c = 0
f = 0
if S[0][0]=='#':
    c = 1
    f = 1
q.put([c,f,0,0])
while not(q.empty()):
    c,f,x,y = q.get()
    for i in range(2):
        nc = c
        nx = x+dx[i]
        ny = y+dy[i]
        if nx>=H or ny>=W:
            continue
        
        if f==0 and (S[nx][ny]=='#'):
            nc = c+1
        
        if nc < dist[nx][ny]: 
            dist[nx][ny] = nc
            nf = S[nx][ny]=='#'
            q.put([nc,nf,nx,ny])
        
print(dist[H-1][W-1])
### BUGGY CODE ###


def InsertionSort(A, n, g):
    cnt = 0

    for i in range(g, n):
        v = A[i]
        j = i - g

        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1

        A[j + g] = v

    return cnt

def ShellSort(A, n):
    total_cnt = 0

    G = [1]
    span = 2

    while span < len(A):
        G.append(span)
        span *= 2

    G.reverse()

    m = len(G)

    for i in range(m):
        total_cnt += InsertionSort(A, n, G[i])

    return m, G, total_cnt

n = int(input())
A = []

for i in range(n):
    A.append(int(input()))

m, G, cnt = ShellSort(A, n)

print(m)
print(*G)
print(cnt)

for a in A:
    print(a)

### FIXED CODE ###


def InsertionSort(A, n, g):
    cnt = 0

    for i in range(g, n):
        v = A[i]
        j = i - g

        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1

        A[j + g] = v

    return cnt

def ShellSort(A, n):
    tot_cnt = 0
    G = [1]
    span = 4

    while span < n:
        G.append(span)
        span = span * 3 + 1

    G.reverse()
    m = len(G)

    for g in G:
        tot_cnt += InsertionSort(A, n, g)

    return m, G, tot_cnt


n = int(input())
A = []

for i in range(n):
    A.append(int(input()))

m, G, tot_cnt = ShellSort(A, n)

print(m)
print(*G)
print(tot_cnt)
print(*A, sep = "\n")
### BUGGY CODE ###

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n = int(input())
    a = input().split()
    b = []
    for i in range(n):
        b.append(a[i])
        b = b[::-1]
    print(' '.join(b))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n = int(input())
    a = input().split()
    b = []
    c = []
    if n%2==0:
        for i in range(n):
            if i%2:
                b.append(a[-i])
            else:
                c.append(a[i])
        print(' '.join(b+c))
    else:
        m = [a[-1]]
        a = a[:-1]
        n -= 1
        for i in range(n):
            if i%2:
                b.append(a[-i])
            else:
                c.append(a[i])
        print(' '.join((b+c+m)[::-1]))

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

from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def yesno(v):
    print(["Yes", "No"][not v])


# エントリーポイント
def main():
    N = input(int)
    A = input([int, N])

    count = dd(int)
    for a in A:
        count[a] += 1
    ans = {}
    for k in count.keys():
        temp = 0
        for v in count.values():
            temp += (v * (v - 1)) // 2
        ans[k] = temp - count[k] + 1
    for a in A:
        print(ans[a])


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


### FIXED CODE ###

from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


def yesno(v):
    print(["Yes", "No"][not v])


# エントリーポイント
def main():
    N = input(int)
    A = input([int, N])

    count = dd(int)
    for a in A:
        count[a] += 1
    sum_ = 0
    for k, v in count.items():
        sum_ += (v * (v - 1)) // 2
    for a in A:
        print(sum_ - count[a] + 1)


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()
### BUGGY CODE ###

#coding:utf-8
import sys
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
for i in range(M):
    b,c=map(int,sys.stdin.readline().split())
    for _ in range(b):
        A.append(c)
A.sort()
A.reverse()        
print(sum(A[:N]))

### FIXED CODE ###

#coding:utf-8
import sys
N,M=map(int,raw_input().split())
A=map(int,raw_input().split())
p=0
Q=[]
for a in A: Q.append((a,1))
for i in range(M):
    b,c=map(int,sys.stdin.readline().split())
    Q.append((c,b))
Q.sort();Q.reverse()
n=0;s=0
for c,b in Q:
    if b+n<=N:
        s+=c*b
        n+=b
    else:
        s+=c*(N-n)
        break
print(s)
### BUGGY CODE ###

from collections import Counter

N = int(input())
words = [Counter(input()) for _ in range(N)]
ans = 0
while True:
    if not words:
        break
    target = words.pop(0)
    same_word_index = [i for i, word in enumerate(words) if target == word]
    loop_sum = len(same_word_index)
    # 同じやつをリストから消す
    [words.pop(index) for index in reversed(same_word_index)]
    # 合計に加算
    ans += int((loop_sum * (loop_sum+1)) / 2)
    
    # 後ろからも
    if not words:
        break
    target = words.pop()
    same_word_index = [i for i, word in enumerate(words) if target == word]
    loop_sum = len(same_word_index)
    # 同じやつをリストから消す
    [words.pop(index) for index in reversed(same_word_index)]
    # 合計に加算
    ans += int((loop_sum * (loop_sum+1)) / 2)

print(ans)

### FIXED CODE ###

from collections import Counter

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

N = int(input())
words = [hashabledict(dict(Counter(input()))) for _ in range(N)]
ans = 0
counter_hash = {}
for counter in words:
    if counter not in counter_hash.keys():
        counter_hash[counter] = 1
    else:
        counter_hash[counter] += 1
 
for count in counter_hash.values():
    ans += int((count * (count-1)) / 2)
print(ans)
### BUGGY CODE ###

s = input()
while "BB" in s or "WW" in s:
	s.replace("BB", "B")
	s.replace("WW", "W")

print(len(s)-1)

### FIXED CODE ###

s = input()
ans = -1
b = ""
for l in s:
	if b != l:
		ans += 1
	b = l
print(ans)
### BUGGY CODE ###

K=int(input())

if K%2==0:
    print(-1)
    exit(0)
mod=7
for i in range(1,pow(10,6)):
    mod=mod%K
    if mod==0:
        print(i)
        exit(0)
    mod+=7*pow(10,i)
    #print(i,mod)


print(-1)

### FIXED CODE ###

K=int(input())

if K%2==0:
    print(-1)
    exit(0)
    
ans=[0]*(pow(10,6)+1)
ans[0]=0

for i in range(1,pow(10,6)):
    ans[i]=(ans[i-1]*10+7)%K
    if ans[i]==0:
        print(i)
        exit(0)

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

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())


### FIXED CODE ###

class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 6) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 2 * (10 ** 6):
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def main():
    K = int(input())
    S = input()
    l = len(S)
    mod = 10**9 + 7
    c = cmbs(mod)
    r = 0
    x25 = 1
    x26 = pow(26, K, mod)
    inv26 = pow(26, mod-2, mod)
    for i in range(K+1):
        r = (r + c.cmb(l+i-1, i) * x25 * x26) % mod
        x25 = x25 * 25 % mod
        x26 = x26 * inv26 % mod
    return r % mod
print(main())
### BUGGY CODE ###

from collections import defaultdict, deque, Counter

N = int(input())

edges = []
counter = Counter()
nodes = defaultdict(set)

for _ in range(N - 1):
    u, v = map(int, input().split(' '))
    counter[u] += 1
    counter[v] += 1
    nodes[u].add(v)
    nodes[v].add(u)
    edges.append((u, v))

K = max(counter.values())
colors = set([1 + k for k in range(K)])

checked = set()
queue = deque([(1, 0)])
edge_colors = {}

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    for v, vc in zip(nodes[u] - checked, colors - {uc}):
        edge_colors[(min(u, v), max(u, v))] = vc
        queue.append((v, vc))

print(K)
for u, v in edges:
    print(edge_colors[(u, v)])


### FIXED CODE ###

from collections import defaultdict, deque, Counter

N = int(input())

counter = Counter()
nodes = defaultdict(list)
edges = []

for i in range(N - 1):
    u, v = map(int, input().split(' '))
    nodes[u].append((v, i))
    nodes[v].append((u, i))
    edges.append((u, v))

K = 0
for node in nodes.values():
    K = max(K, len(node))

checked = set()
queue = deque([(1, 0)])
edge_colors = [0] * N

while queue:
    u, uc = queue.popleft()
    checked.add(u)
    color = 1
    for v, e in nodes[u]:
        if v in checked:
            continue
        if color == uc:
            color += 1
        edge_colors[e] = color
        queue.append((v, color))
        color += 1

print(K)
for i in range(N - 1):
    print(edge_colors[i])