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

import numpy as np
def solve():
    h, w = map(int, input().split())
    S = list(input() + '#' for _ in range(h)) + ['#' * (w + 1)]
    H = np.zeros([h + 1, w], dtype=np.int)
    W = np.zeros([h + 1, w], dtype=np.int)
    for r in range(h):
        c = 0
        while c < w:
            if S[r][c] == '.':
                t = S[r][c:].find('#')
                for j in range(c, c + t):
                    W[r][j] = t
                c += t
            c += 1
    for c in range(w):
        r = 0
        while r < h:
            if S[r][c] == '.':
                t = r + 1
                cnt = 1
                while S[t][c] == '.':
                    t += 1
                    cnt += 1
                for i in range(r, t):
                    H[i][c] = cnt
                r = t
            r += 1
    ans = 0
    for r in range(h):
        for c in range(w):
            ans = max(ans, H[r][c] + W[r][c] - 1)
    print(ans)
solve()


### FIXED CODE ###

def solve():
    h, w = map(int, input().split())
    S = list(input() + '#' for _ in range(h)) + ['#' * (w + 1)]
    H = [[0] * w for _ in range(h + 1)]
    W = [[0] * w for _ in range(h + 1)]
    for r in range(h):
        c = 0
        while c < w:
            if S[r][c] == '.':
                t = S[r][c:].find('#')
                for j in range(c, c + t):
                    W[r][j] = t
                c += t
            c += 1
    for c in range(w):
        r = 0
        while r < h:
            if S[r][c] == '.':
                t = r + 1
                cnt = 1
                while S[t][c] == '.':
                    t += 1
                    cnt += 1
                for i in range(r, t):
                    H[i][c] = cnt
                r = t
            r += 1
    ans = 0
    for r in range(h):
        for c in range(w):
            ans = max(ans, H[r][c] + W[r][c] - 1)
    print(ans)
solve()
### BUGGY CODE ###

import math , sys 
from collections import deque

N = int( input() )
Cs = list( map( int , input().split() ))
Cs.sort(reverse=True)

conf=0
d=deque()
i=0
while len(Cs)>0:
    tar=Cs.pop(0)
    #print(tar,Cs)
    if i==0:
        conf+=tar
        d.append(tar)
        i+=1
    elif i==1:
        #conf+=d[0]
        #d.append(tar)
        Ds=deque([tar,tar])
        i+=1
    else:
        #print(Ds,d)
        c=max(Ds)
        conf+=c
        ind=Ds.index(c)
        #d.insert(ind,tar)
        Ds.insert(ind,tar)
        Ds[ind+1]=tar
        #print(Ds,d)
print(conf)

### FIXED CODE ###

import math , sys 
from collections import deque

N = int( input() )
Cs = list( map( int , input().split() ))
Cs.sort(reverse=True)

ans = Cs.pop(0)
i = 1
Q  = (N-2)//2
R = (N-2) % 2
ans += sum([Cs[i]*2 for i in range(Q)])
if R==1:
    ans+=Cs[Q]
print(ans)
### BUGGY CODE ###

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)
val1 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x *= n-i % (10 ** 9 + 7)
    y *= i+1 % (10 ** 9 + 7)

val2 = x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7) % (10 ** 9 + 7)
print(wa - val1 - val2)

### FIXED CODE ###

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

#制限なしで全ての花束の作り方
wa = pow(2, n, 10 ** 9 + 7) - 1

#a本の花束の作り方
#val1 = comb(n, a, exact=True)
#val2 = comb(n, b, exact = True)

x = 1
y = 1
for i in range(a):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)
val1 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

x = 1
y = 1
for i in range(b):
    x = (x * (n-i)) % (10 ** 9 + 7)
    y = (y * (i+1)) % (10 ** 9 + 7)

val2 = (x * pow(y, 10 ** 9 + 7 - 2, 10 ** 9 + 7)) % (10 ** 9 + 7)

ans = wa - val1 - val2
for i in range(100):
    if ans < 0:
        ans += 10 ** 9 + 7
print(ans)
### BUGGY CODE ###

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
def p_comb(a, b, c, d):
    a = (1<<a) - 1
    b = (1<<b) - 1
    c = (1<<c) - 1
    d = (1<<d) - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)   


### FIXED CODE ###

N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
from operator import itemgetter
def solve():
    p_list = XY[:]

    # y座標の圧縮
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    # xでソート
    p_list= sorted(p_list)

    # ある点が四角に含まれる場合の総数を求めるメソッド
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    # a,bを求める
    bit = Bit(N)
    ans = 0
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a = tmp
        b = i-tmp
        c = r-tmp-1
        d = (N-r+1)-(i-tmp)-1
        bit.add(r, 1)
        _a = power[a] - 1
        _b = power[b] - 1
        _c = power[c] - 1
        _d = power[d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()
### BUGGY CODE ###

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
num = {0: int(0 not in broken), 1: int(1 not in broken)}



for i in range(2, n):
    if i in broken:
        num[i] = 0
    else:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
broken = []
for i in range(m):
    broken.append(int(input()))
    
num = [-1] * (n + 1)
num[0] = 1
num[1] = 1


for i in broken:
    num[i] = 0

for i in range(2, n):
    if num[i] == -1:
        num[i] = (num[i-1] + num[i-2])%1000000007
        
if n <= 1:
    print(num[n])
else:
    print((num[n-1]+num[n-2])%1000000007)
### BUGGY CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))




### FIXED CODE ###

from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    dp1=dp[:]
    for j in range(1,len(dp)):
        k=dp[j-1]*(1-P[i])+dp[j]*(P[i])
        dp1[j]=k
    dp=dp1[:]
print(sum(dp))
### BUGGY CODE ###

import numpy as np

N = int(input())
Ps = list(map(int, input().split()))
Ps = np.array(Ps)
count = 0

for i in range(N):
    low = Ps[i]
    tmp = Ps[:i] - low

    if (np.count_nonzero(Ps[:i] >= low) == i):
        count += 1

print(count)

### FIXED CODE ###

N = int(input())
Ps = list(map(int, input().split()))
count = 0
min = Ps[0]+1

for i in range(N):
    if (Ps[i] < min):
        min = Ps[i]
        count += 1

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

equal = np.empty((W-1,H,H),dtype=np.bool)
for n in range(W-1):
    equal[n,:,:] = (C[n][:,None] == C[n+1][None,:])
dp_1 = np.zeros((W-1,H+H+1,H+H+1),dtype=np.int64)
L = np.arange(1,H+1)
R = np.arange(1,H+1)
dp_1[:,R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
np.cumsum(dp_1,out=dp_1,axis=2)

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

from itertools import permutations

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


ans = S.count('R') * S.count('G') * S.count('B')
for i,j in permutations(range(N), 2):
  if (i+j)%2 or i>=j: continue
  a = S[i]
  b = S[j]
  k = (i+j)//2
  if sorted([a,S[k],b]) == ['B','G','R']:
    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 ###

import math
A, B, N = map(int, input().split())
ans = 0

if N > 10000:
    for x in range(N+1, int(N/2), -1):
        tmpans = math.floor((A * x)/B) - (A * math.floor(x/B))
        ans = max(tmpans, ans)
    print(ans)
else:
    for x in range(1, N+1):
        tmpans = math.floor((A * x)/B) - (A * math.floor(x/B))
        ans = max(tmpans, ans)
    print(ans)


### FIXED CODE ###

import math

A, B, N = map(int, input().split())

if N < B:
    x = N
else:
    x = B - 1

def check(x):
    return math.floor((A * x) / B)
            
print(check(x))
### BUGGY CODE ###

n = int(input())
MAXN = 110000

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

for i in range(1, n+2):
    power6 = 1
    power9 = 1
    for j in range(1, n+1):
        if i >= power6:
            dp[i] = min(dp[i], dp[i-power6]+1)
            power6 *= 6

    for k in range(1, n+1):
        if i >= power9:
            dp[i] = min(dp[i], dp[i-power9]+1)
            power9 *= 9

print(dp[n])


### FIXED CODE ###

n = int(input())
MAXN = 110000

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

for i in range(1, n+2):
    for j in range(7):
        dp[i] = min(dp[i], dp[i-pow(6, j)]+1)
    for k in range(6):
        dp[i] = min(dp[i], dp[i-pow(9, k)]+1)

print(dp[n])
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        history = [1]
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                b = len(d[i]) - 1
                if a < b:
                    print(0)
                    break
                children |= d[i]
                if b == 0:
                    continue
                ans *= perm(a, b)
            else:
                for i in history:
                    if i in children:
                        children.remove(i)
                if len(children) == 0:
                    print(ans % mod)
                    break
                history, root = root, children
                continue
            break


### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(1,A+B+1):
        ans = ans*i%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
    for i in range(1,B+1):
        ans = ans*mod_inv(i,P)%P
print(ans)


### FIXED CODE ###

X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)
### BUGGY CODE ###

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

dp = [[0]*100010 for i in range(N+10)]
for i in range(N):
    for now_w in range(W+1):
        if (now_w >= w[i]):
            dp[i+1][now_w] = max(dp[i][now_w-w[i]] + v[i], dp[i][now_w])
        else:
            dp[i+1][now_w] = dp[i][now_w]

print(dp[N][W])

### FIXED CODE ###

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

dp = [[0]*100010 for i in range(N+10)]
for i in range(N):
    for now_w in range(W+1):
        if (now_w >= w[i]):
            dp[i+1][now_w] = max(dp[i][now_w-w[i]] + v[i], dp[i][now_w])
        else:
            dp[i+1][now_w] = dp[i][now_w]

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

import heapq
import collections
import heapq
def input_as_int():
    return list(map(int,input().split()))


def get_comb(n):  # n C n まで

    fac = get_fact(n)
    com  = [["error" for _ in range(n+1)] for _ in range (n + 1)]
    for i in range(n + 1):
        for j in range(i + 1):
            if  i >= j:
                com[i][j] = fac[i] // (fac[i-j] * fac[j])

    return com


def get_fact(n):
    temp = 1
    fac = [1]
    for i in range(1, n + 1):
        temp *= i
        fac.append(temp)
    return fac

def prime_method(graph):
    start = graph[0]
    n = len(graph)
    went = [False] * n #n個の点に行ったかという話
    edges = []
    for temp in start:
        heapq.heappush(edges,temp)
    went[0] = True
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if went[minedge[1]]:
            continue
        v = minedge[1]
        for temp in graph[v]:
            if not went[temp[1]]: #その頂点に行ってなければ
                heapq.heappush(edges,temp)
        went[v] = True
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある

def get_graph():
    n = input()
    graph = [input_as_int() for _ in range(n)]


    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
cities  = [(input_as_int(),i) for i in range(n)]
graph = [[] for _ in  range(n)]

cities.sort(key = lambda x:x[0][0])
citiesX = cities
for city1,city2 in zip(citiesX[0:-1],citiesX[1:]):
    no1 = city1[1]
    no2 = city2[1]
    graph[no1].append([abs(city1[0][0] - city2[0][0]),no2])
    graph[no2].append([abs(city1[0][0] - city2[0][0]),no1])
cities.sort(key =lambda x:x[0][1])
for city1,city2 in zip(cities[0:-1],cities[1:]):
    no1 = city1[1]
    no2 = city2[1]
    graph[no1].append([abs(city1[0][1] - city2[0][1]),no2])
    graph[no2].append([abs(city1[0][1] - city2[0][1]),no1])


print(prime_method(graph))

### FIXED CODE ###


import heapq

def prime_method():
    not_went = [True] * n  # n個の点に行ったかという話
    edges = []
    start = graph[0]
    for e in start:
        heapq.heappush(edges,e)
    not_went[0] = False
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if not not_went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        not_went[v] = False
        for temp in gv:
            if not_went[temp[1]]:  # その頂点に行ってなければ
                heapq.heappush(edges, temp)
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
graph = [[] for i in  range(n)]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))


citiesX=sorted(cities,key=lambda x:x[0])
citiesY=sorted(cities,key=lambda x:x[1])

for i in range(n-1):
    graph[citiesX[i][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i+1][2]))
    graph[citiesX[i+1][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i][2]))
    graph[citiesY[i][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i+1][2]))
    graph[citiesY[i+1][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i][2]))
print(prime_method())
### BUGGY CODE ###

from collections import defaultdict
n=int(input())
col=[{}for i in range(n)]
edges=[set() for i in range(n)]
ret=[0]*(n-1)
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].add((s-1,i));edges[s-1].add((a-1,i))
m=0
ind=-1
for i in range(n):
    if m<len(edges[i]):
        ind=i
        m=len(edges[i])
print(m)
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i,e in zip(range(1,m+1),edges[ind]):
    col[e[0]][ind]=i
    dq.append(e[0])
    ret[e[1]]=i
x=set(range(1,m+1))
while dq:
    a=dq.popleft()
    c=x-set(col[a].values())
    ng=set(col[a].keys())
    for to,num in edges[a]:
        if to not in ng:
            cc=c.pop()
            col[to][a]=cc
            dq.append(to)
            ret[num]=cc
        
print(*ret,sep="\n")

### FIXED CODE ###

n=int(input())
edges=[[] for i in range(1+n)]
e={}
for i in range(n-1):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    edges[__].append(_)
    e[(_,__)]=i
    e[(__,_)]=i
    """
"""#weighted->erase
f=max(len(j)for j in edges)
print(f)
ret=[0]*(n-1)
from collections import deque
dq=deque([(1,1)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
while dq:
    a,c=dq.popleft()
    for to in edges[a]:
        if ret[e[(a,to)]]:continue
        ret[e[(a,to)]]=c
        c=c%f+1
        dq.append((to,c))
        
print(*ret,sep="\n")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    dp = []
    for _ in range(N):
        l = [0]*(W + 1)
        dp.append(l)
    
    # dp[0][]だけ初期化
    for j in range(W + 1):
        dp[0][j] = v[0] if j >= w[0] else 0

    for i in range(1, N):
        for j in range(W + 1):
            if j >= w[i]:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
                
    print(dp[N - 1][W])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):

    dp = []
    for _ in range(N):
        l = [0]*(W + 1)
        dp.append(l)
    
    # dp[0][]だけ初期化
    for j in range(W + 1):
        dp[0][j] = v[0] if j >= w[0] else 0

    for i in range(1, N):
        for j in range(W + 1):
            if j >= w[i]:
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
                
    print(dp[N - 1][W])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()