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

n, l = map(int, input().split())
ss = [input() for _ in range(n)]
prefix = set()
for s in ss:
	for i in range(len(s)):
		prefix.add(s[:i+1])
grundy = 0
for p in list(prefix):
	if p[-1] == "0":
		t = p[:-1] + "1"
	else:
		t = p[:-1] + "0"
	if t not in prefix:
		grundy ^= (l-len(t)+1) & (-l+len(t)-1)

if grundy == 0:
	print("Bob")
else:
	print("Alice")

### FIXED CODE ###

import sys
#from collections import defaultdict
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]
n, l = map(int, input().split())
ss = [list(input())[::-1] for _ in range(n)]

def addTree(tree, sentence):
	if not sentence:
		return None   

	if sentence[-1] not in tree:
		tree[sentence[-1]] = {}

	p = sentence.pop()
	tree[p] = addTree(tree[p], sentence)

	return tree

def createTree(sentences):    
	tree = {}
	for sentence in sentences:
		tree = addTree(tree, sentence)

	return tree

tree = createTree(ss)
#print(tree)

grundy = 0
def dfs(cur, level):
	global grundy
	if cur is None:
		return
	elif len(cur) == 1:
		grundy ^= (l-level) & (-l+level)
	for k in cur.keys():
		dfs(cur[k], level+1)
	return
	
dfs(tree, 0)

if grundy == 0:
	print("Bob")
else:
	print("Alice")
### BUGGY CODE ###

import sys

MOD = 998244353

N, S = map(int, input().split())
X = [int(x) for x in sys.stdin.readline().split()]

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

for i in range(1, N+1):
    xi = X[i-1]
    for j in range(S+1):
        # xi を U に加えない場合
        dp[i][j] += dp[i-1][j]*2 % MOD # T に加える／加えない

        # xi を U に加える場合
        if j+xi > S: continue
        dp[i][j+xi] += dp[i-1][j] % MOD

print(dp[N][S] % MOD)

### FIXED CODE ###

import sys

MOD = 998244353

def main():
    N, S = map(int, input().split())
    X = [int(x) for x in sys.stdin.readline().split()]

    # dp = np.zeros((N+1)*(S+1), dtype=np.int).reshape((N+1),(S+1))
    dp = [[0 for _ in range(S+1)] for _ in range(N+1)]

    dp[0][0] = 1

    for i in range(N):
        xi = X[i]
        # xi を U に加えない場合
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]*2  # T に加える／加えない
            dp[i+1][j] %= MOD
            # xi を U に加える場合
            if j+xi > S: continue
            dp[i+1][j+xi] += dp[i][j]
            dp[i+1][j+xi] %= MOD

    print(dp[N][S] % MOD)

main()
### BUGGY CODE ###

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[a] == float("inf"):
				continue

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(m)]


def bellman_ford(s, g):
	dist = [float("inf")] * n
	dist[s] = 0
	negative = [False] * n
	for i in range(2 * n):
		for a, b, c in abc:
			a -= 1
			b -= 1
			c = -c

			if dist[b] > dist[a] + c:
				dist[b] = dist[a] + c
				if i >= n:
					negative[b] = True

	if negative[g]:
		ret = "inf"

	else:
		ret = -dist[g]

	return ret


ans = bellman_ford(0, n - 1)
print(ans)
### BUGGY CODE ###

[N, X, Y] = input().split()
N = int(N)
X = int(X)
Y = int(Y)
dist_list = []

for i in range(N):
    for j in range(i+1, N):
        a = j - i
        b = abs(i+1 - X) + abs(j+1 -Y) + 1
        if a > b:
            dist_list.append(b)
        else:
            dist_list.append(a)

for k in range(N-1):
    print(dist_list.count(k+1))



### FIXED CODE ###

N, X, Y = map(int, input().split())
dist_list = [0]*N

for i in range(N-1):
    for j in range(i+1, N):
        a = j - i
        b = abs(i+1 - X) + abs(j+1 -Y) + 1
        dist_list[min(a,b)] += 1

for k in range(N-1):
    print(dist_list[k+1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = map(int, input().split())
    Dh, Dw = Dh - 1, Dw - 1
    maze = [input() for i in range(H)]
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    dist = visited[Dh][Dw]

    print(dist if dist != inf else -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque
from math import inf


def input(): return sys.stdin.readline().strip()


def bfs(maze, Ch, Cw, Dh, Dw, H, W):
    visited = [[inf] * W for i in range(H)]
    queue = deque([[Ch, Cw]])
    visited[Ch][Cw] = 0

    dy_dx0 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    dy_dx1 = [[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 queue:
        y, x = queue.popleft()
        if [y, x] == [Dh, Dw]:
            break
        for j, k in dy_dx0:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[y][x] < visited[new_y][new_x]:
                visited[new_y][new_x] = visited[y][x]
                queue.appendleft([new_y, new_x])
        for j, k in dy_dx1:
            new_y, new_x = y + j, x + k
            if 0 <= new_y < H and 0 <= new_x < W and maze[new_y][new_x] == "." and visited[new_y][new_x] == inf:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    return visited[Dh][Dw]


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    maze = [input() for i in range(H)]

    dist = bfs(maze, Ch - 1, Cw - 1, Dh - 1, Dw - 1, H, W)

    print(dist if dist != inf else -1)


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

n=int(input())
A=[list(map(int,input().split()))for _ in range(n)]
S=[0]*(1<<n)
for i in range(1<<n):
	for j in range(n):
		if i&(1<<j):
			for k in range(j):
				if i&(1<<k):
					S[i]+=A[j][k]
dp=[-10**9]*(1<<n)
dp[0]=0
for i in range(1,1<<n):
	j=i
	b=i.bit_length()
	while j.bit_length()==b:
		dp[i]=max(dp[i],S[j]+dp[i-j])
	j=i&(j-1)
print(dp[-1])

### FIXED CODE ###

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

S=[0]*(1<<n)
for i in range(1<<n):
    for j in range(n):
        if i&(1<<j):
            for k in range(n):
                if i&(1<<k):
                    S[i]+=A[j][k]
dp=[-10**9]*(1<<n)
dp[0]=0
for i in range(1,1<<n):
    j=i
    b=i.bit_length()
    while j.bit_length()==b:
        dp[i]=max(dp[i],S[j]+dp[i-j])
        j=i&(j-1)
print(dp[-1]//2)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
k=min(K,X*Y)
AB=sorted([a+b for a in A for b in B],reverse=True)[:k]
ABC=sorted([ab+c for ab in AB for c in C],reverse=True)[:K]
for x in ABC:
  print(x)

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=sorted(list(map(int,input().split())),reverse=True)
B=sorted(list(map(int,input().split())),reverse=True)
C=sorted(list(map(int,input().split())),reverse=True)
ans=[]
for i in range(X):
  if i+1>K:
    break
  for j in range(Y):
    if (i+1)*(j+1)>K:
      break
    for k in range(Z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      ans.append(A[i]+B[j]+C[k])
ans=sorted(ans,reverse=True)
for a in ans[:K]:
  print(a)
### BUGGY CODE ###

import itertools

A, B, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []

for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]

for i in range(M):
    ans.append(a[x[i]-1] + b[y[i]-1] - c[i])

a = set(a)
b = set(b)
temp = list(itertools.product(a, b))
for i,j in temp:
    ans.append(i+j)

print(min(ans))

### FIXED CODE ###

A, B, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []
ans.append(min(a) + min(b))
for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]

for i in range(M):
    ans.append(a[x[i] - 1] + b[y[i] - 1] - c[i])

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

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

for i in range(1, n+1):
    ans.append(a.index(i)+1)

print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0]*n

for i in range(n):
    ans[a[i]-1] = i+1

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

import sys
input = sys.stdin.readline #for input speed

H, W = map(int, input().split())
M = [list(input().strip()) for _ in range(H)]
M_yoko = [[0 for _ in range(W)] for _ in range(H)]
M_tate = [[0 for _ in range(W)] for _ in range(H)]

for row in range(H):
    walls = [-1]
    for col in range(W):
        if M[row][col] == '#':
            walls.append(col)
    walls.append(W)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_yoko[row][j] = ed - st - 1

for col in range(W):
    walls = [-1]
    for row in range(H):
        if M[row][col] == '#':
            walls.append(row)
    walls.append(H)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_tate[j][col] = ed - st - 1

ans = 0
for row in range(H):
    for col in range(W):
        ans = max(ans, M_yoko[row][col] + M_tate[row][col])

print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
M = [list(input().strip()) for _ in range(H)]
M_yoko = [[0 for _ in range(W)] for _ in range(H)]
M_tate = [[0 for _ in range(W)] for _ in range(H)]

for row in range(H):
    walls = [-1]
    for col in range(W):
        if M[row][col] == '#':
            walls.append(col)
    walls.append(W)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_yoko[row][j] = ed - st - 1

for col in range(W):
    walls = [-1]
    for row in range(H):
        if M[row][col] == '#':
            walls.append(row)
    walls.append(H)
    for i in range(len(walls)-1):
        st = walls[i]
        ed = walls[i+1]
        for j in range(st+1, ed):
            M_tate[j][col] = ed - st - 1

ans = 0
for row in range(H):
    for col in range(W):
        ans = max(ans, M_yoko[row][col] + M_tate[row][col])

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

S = input()
K = int(input())
Ans = ''
for s in S[:-1]:
    if (123 - ord(s)) <= K:
        Ans += 'a'
        K -= 123 - ord(s)
    else:
        Ans += s

K %= 26
if ord(S[-1]) + K >= 123:
    Ans += chr(ord(S[-1]) + K - 26)
else:
    Ans += chr(ord(S[-1]) + K)


print(Ans)

### FIXED CODE ###

S = input()
K = int(input())
Ans = []
for s in S[:-1]:
    if s == 'a':
        Ans.append('a')
        continue
    if (123 - ord(s)) <= K:
        Ans.append('a')
        K -= 123 - ord(s)
    else:
        Ans.append(s)

K %= 26
if ord(S[-1]) + K >= 123:
    Ans.append(chr(ord(S[-1]) + K - 26))
else:
    Ans.append(chr(ord(S[-1]) + K))


print(''.join(Ans))
### BUGGY CODE ###

import itertools
A,B=map(int,input().split())

C=[1]
for i in range(2,min(A,B)+1):
    if A % i == 0 and B % i == 0:
        C.append(i)
#print(C)

#for i in itertools.combinations(C, 2):
#    print(i)

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    if a == 1:
        return 1
    else:
        return 0
NG=[]
ans=0

for i in itertools.combinations(C, 2):
    a,b=i
    if a in NG:
        continue
    if b in NG:
        continue

    z=gcd(a,b)
    #print(a,b)
    #print(z)
    
    if z == 0:
        NG.append(max(a,b))

print(len(C)-len(NG))

    



### FIXED CODE ###

import fractions
import collections
   
A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(gcd))
print(len(list(c.keys()))+1)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K+1):
  if i <= S:
    for j in range(K+1):
      if j <= S:
        if S - i - j <= K and S - i - j >= 0:
          count += 1        
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        if S - i - j <= K and S - i - j >= 0:
          count += 1        
print(count)
### 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 and S[nh][nw] == '.':
                if cnt[nh][nw] > cnt[h][w]:
                    cnt[nh][nw] = cnt[h][w]
                    Q.appendleft([nh,nw])
        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 ###

N,W = map(int,input().split())
weights = N*[0]
values = N*[0]
for i in range(N):
    weights[i], values[i] = map(int,input().split())

inf = float("inf")
dp = [[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

for i in range(N):
    for w in range(W+1):
        if weights[i] <= w:
            dp[i+1][w]=max(dp[i][w-weights[i]]+values[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]

print(dp[N][W])
#print(dp)

### FIXED CODE ###

N,W = map(int,input().split())
v1 = []
v2 = []
v3 = []
v4 = []
w1,v = map(int,input().split())
v1.append(v)
for i in range(N-1):
    w,v = map(int,input().split())
    if w == w1:
        v1.append(v)
    elif w == w1 + 1:
        v2.append(v)
    elif w == w1 + 2:
        v3.append(v)
    elif w == w1 + 3:
        v4.append(v)
v1.sort(reverse=True)
v2.sort(reverse=True)
v3.sort(reverse=True)
v4.sort(reverse=True)

l1 = len(v1)
l2 = len(v2)
l3 = len(v3)
l4 = len(v4)
ans = 0
for i in range(l1+1):
    for j in range(l2+1):
        for k in range(l3+1):
            for l in range(l4+1):

                if i*w1 + j*(w1+1) + k*(w1+2) + l*(w1+3) <= W:
                    temp = sum(v1[:i]) + sum(v2[:j]) + sum(v3[:k]) + sum(v4[:l])
                    ans = max(ans,temp)
print(ans)
### BUGGY CODE ###

from collections import Counter
from itertools import product
H, W, M = list(map(int, input().split()))
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = list(map(int, input().split()))
hc = Counter(h)
wc = Counter(w)
hmax = max(hc.values())
wmax = max(wc.values())
lh = [k[0] for k in hc.items() if k[1] == hmax]
lw = [k[0] for k in wc.items() if k[1] == wmax]
# print(lh,lw)
S = set(product(lh, lw))
# print(S)

for i in range(M):
    if (h[i], w[i]) in S:
        S -= {(h[i], w[i])}
if S:
    print(hmax+wmax)
else:
    print(hmax+wmax-1)

### FIXED CODE ###

from collections import Counter
H, W, M = list(map(int, input().split()))
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = list(map(int, input().split()))
hc = Counter(h)
wc = Counter(w)
hmax = max(hc.values())
wmax = max(wc.values())
lh = {k[0] for k in hc.items() if k[1] == hmax}
lw = {k[0] for k in wc.items() if k[1] == wmax}

ct = 0
for i in range(M):
    if h[i] in lh and w[i] in lw:
        ct += 1
if ct >= len(lh)*len(lw):
    print(hmax+wmax-1)
else:
    print(hmax+wmax)
### BUGGY CODE ###

import math
inf=0
def segtree(a): #RMQ(Range Minimum Query)
    #bi=高さ　bi2=最下段の個数
    global bi 
    bi=math.ceil(math.log2(len(a)))+1
    global bi2
    bi2=2**(bi-1)
    seg=[inf]*(2*bi2-1)
    for i in range(len(a)):
        seg[bi2+i-1]=a[i]
    for i in range(bi-1):
        for j in range(2**(bi-i-2)):
            b=2**(bi-i-2)-1+j
            seg[b]=math.gcd(seg[2*b+1],seg[2*b+2])
    return seg

def seg_update(loc,val): #locの値をvalueに更新
    loc+=bi2-1
    seg[loc]=val
    while True:
        seg[loc]=math.gcd(val,seg[loc])
        if loc==0:
            break
        loc=(loc-1)//2

def seg_find(l,r,tmp=0): #[l,r)の最小値を求める
    a=bi-math.ceil(math.log2(tmp+2))+1
    nl=2**(a-1)*(tmp-(2**(bi-a))+1)
    nr=nl+2**(a-1)
    if nr<=l or nl>=r:
        return inf
    elif l<=nl and nr<=r:
        return seg[tmp]
    else:
        return math.gcd(seg_find(l,r,tmp*2+1),seg_find(l,r,tmp*2+2))

n=int(input())
seg=segtree(list(map(int,input().split())))
ans=0
for i in range(n):
    ans=max(ans,math.gcd(seg_find(0,i),seg_find(i+1,n)))
print(ans)

### FIXED CODE ###

import math
inf=0
def segtree(a): #RMQ(Range Minimum Query)
    #bi=高さ　bi2=最下段の個数
    global bi 
    bi=math.ceil(math.log2(len(a)))+1
    global bi2
    bi2=2**(bi-1)
    seg=[inf]*(2*bi2-1)
    for i in range(len(a)):
        seg[bi2+i-1]=a[i]
    for i in range(bi-1):
        for j in range(2**(bi-i-2)):
            b=2**(bi-i-2)-1+j
            seg[b]=math.gcd(seg[2*b+1],seg[2*b+2])
    return seg

def seg_update(loc,val): #locの値をvalueに更新
    loc+=bi2-1
    seg[loc]=val
    while True:
        seg[loc]=math.gcd(val,seg[loc])
        if loc==0:
            break
        loc=(loc-1)//2

def seg_find(l,r,tmp=0): #[l,r)の最小値を求める
    a=bi-math.ceil(math.log2(tmp+2))+1
    nl=2**(a-1)*(tmp-(2**(bi-a))+1)
    nr=nl+2**(a-1)
    if nr<=l or nl>=r:
        return inf
    elif l<=nl and nr<=r:
        return seg[tmp]
    else:
        return math.gcd(seg_find(l,r,tmp*2+1),seg_find(l,r,tmp*2+2))

n=int(input())
seg=segtree(list(map(int,input().split())))
ans=0
for i in range(n):
    ans=max(ans,math.gcd(seg_find(0,i),seg_find(i+1,n)))
print(ans)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for a1,list1 in l:
    color=1
    for b1 in list1:
        if a1>b1:
            a,b=b1,a1
        else:
            a,b=a1,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
ans=[]
for line in ab:
    ans.append(d2[line])
print(*ans,sep="\n")

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
    d[b].append(a)

l=list(d.items())
l.sort(key=lambda x:-len(x[1]))
m=len(l[0][1])

d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for node,list1 in l:
    a=node
    color=1
#     print(node,list1)
    for b1 in list1:
        if node>b1:
            a,b=b1,node
        else:
            a,b=node,b1
#         print(a,b)
        if d2[(a,b)]!=0:
            continue
        else:
            while color in c[a] or color in c[b]:
                color+=1 
            d2[(a,b)]=color
            c[a].append(color)
            c[b].append(color)
            color+=1
#     print(d2)
print(m)
for line in ab:
    print(d2[line])