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

def main():
    import numpy as np
    from itertools import product
    H, W, K = map(int, input().split())
    G = np.array([list(map(int, list(input()))) for _ in range(H)])
    #print(np.count_nonzero(G[:, 1:1]))
    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1]  + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        base_w = 0
        w = 0
        #print(grids)
        while w <= W:
            #print(base_w, w)
            for grid in grids:
                if np.count_nonzero(grid[:, base_w: w]) > K:
                    #print('out', base_w, w)
                    base_w = w - 1
                    w = base_w
                    tmp_ans += 1
                    break
            else:
                w += 1
        # print('tmp', tmp_ans)
        # print("\n")
        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


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

n,k = map(int,input().split())
P = [-1] + list(map(int,input().split())) + [10**6]
Q = [''.join(map(str,P))]
for i in range(1,n-k+1):
    q = P[:i] + sorted(P[i:i+k]) + P[i+k:]
    Q += [''.join(map(str,q))]
print(len(set(Q)))

### FIXED CODE ###

class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


N, K = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))

bit = BinaryIndexedTree(N + 1)
count = 1

for i in range(K):
    bit.add(P[i], 1)

for i in range(N - K):
    mi = bit.bisect_left(1)
    ma = bit.bisect_left(K)
    if P[i] != mi or P[K + i] < ma:
        count += 1
    bit.add(P[i], -1)
    bit.add(P[K + i], 1)

inc = 1
incseq = 0

for i in range(N - 1):
    if P[i] < P[i + 1]:
        inc += 1
        if inc == K:
            incseq += 1
    else:
        inc = 1

print(count - max(0, incseq - 1))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    def check(lst):
        for i in range(N):
            if lst[i] != N:
                return False
        return True

    def move(lst):
        tmp = [0] * (N + 1)
        for i in range(N):
            a = lst[i]
            left = max(0, i - a)
            right = min(N, i + a + 1)
            tmp[left] += 1
            tmp[right] -= 1
        for i in range(N):
            tmp[i + 1] += tmp[i]
        return tmp

    for i in range(K):
        A = move(A)
        if check(A):
            # print (i)
            break

    print (*A[:-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def check(lst):
    for i in range(N):
        if lst[i] != N:
            return False
    return True

def move(lst):
    tmp = [0] * (N + 1)
    for i in range(N):
        a = lst[i]
        left = max(0, i - a)
        right = min(N, i + a + 1)
        tmp[left] += 1
        tmp[right] -= 1
    for i in range(N):
        tmp[i + 1] += tmp[i]
    return tmp

for i in range(K):
    A = move(A)
    if check(A):
        # print (i)
        break

print (*A[:-1])
### BUGGY CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in range(1,1001)]

mx=0
ind=0
for i in range(N-K+1):
  if mx<max(mx,sum(p[i:i+K])):
    ind=i
    mx=max(mx,sum(p[i:i+K]))



ans=0
# for i in range(ind,ind+K):
#   ans+=ex[p[i]-1]
i=ind
while(K):
  ans+=ex[p[i]-1]
  i+=1
  K-=1

print(ans)




### FIXED CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in p]
ruiseki=[0]
ans=0

for i in range(N):
  ruiseki.append(ruiseki[i]+ex[i])


for i in range(N+1-K):
  if ans<ruiseki[i+K]-ruiseki[i]:
    ans=ruiseki[i+K]-ruiseki[i]
print(ans)
### BUGGY CODE ###

#import math
#
#def combinations_count(n, r=2):
#    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) if n > 1 else 0

N = int(input())
A = list(map(int, input().split()))
#dp = [0]*(N+1)
dp = [int(n*(n-1)/2) for n in range(N+1)]
cnt_org = {}

for a in A:
  key = str(a)
  cnt_org[key] = cnt_org.get(key, 0) + 1

for k in range(N):
  cnt = cnt_org.copy()
  cnt[str(A[k])] -= 1
  ans = 0
  for v in cnt.values():
#    if dp[v] == 0:
#      dp[v] = combinations_count(v)
    ans += dp[v]
  
  print(ans)




### FIXED CODE ###

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

dp = [int(n*(n-1)/2) for n in range(N+1)]
cnt_org = [0]*(N+1)

for a in A:
  key = a
  cnt_org[a] += 1 

base = sum([dp[c] for c in cnt_org])

for k in range(N):
  diff = dp[cnt_org[A[k]]] - dp[cnt_org[A[k]]-1]
  print(base - diff)
### BUGGY CODE ###

H, W = list(map(int, input().split(' ')))
xs = []
for i in range(H):
    xs.append(list(map(int, input().split(' '))))
# best でなくても良い？
ans = []  # x,y -> p, q
seeds = []
for i in range(H):  # 500
    for j in range(W):  # 500
        if xs[i][j] % 2 != 0:
            seeds.append((i, j))
used = {}
def f(st, ed):
    res = []
    while(st != ed):
        while(st[0] > ed[0]):
            if (st[0]-1, st[1]) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1-1, st[1]+1))
            st = (st[0]-1, st[1])
            used[st] = True
        while(st[0] < ed[0]):
            if (st[0]+1, st[1]) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1+1, st[1]+1))
            st = (st[0]+1, st[1])
            used[st] = True
        while(st[1] > ed[1]):
            if (st[0], st[1]-1) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1, st[1]+1-1))
            st = (st[0], st[1]-1)
            used[st] = True
        while(st[1] < ed[1]):
            if (st[0], st[1]+1) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1, st[1]+1+1))
            st = (st[0], st[1]+1)
            used[st] = True
    return res

ans = []
# print (seeds)
seeds = sorted(seeds, key=lambda x:(x[0] + x[1] + (x[1] * 10000) + (x[0] == W-1) * 50000))
# print (seeds)
for i in range(0, len(seeds)-1, 2):
    st = seeds[i]
    ed = seeds[i+1]
    ans += f(st, ed)
print(len(ans))
print('\n'.join(ans))


### FIXED CODE ###

H, W = list(map(int, input().split(' ')))
xs = []
for i in range(H):
    xs.append(list(map(int, input().split(' '))))
# best でなくても良い？
ans = []  # x,y -> p, q
seeds = []
for i in range(H):  # 500
    for j in range(W):  # 500
        if xs[i][j] % 2 != 0:
            seeds.append((i, j))
used = {}
def f(st, ed):
    res = []
    while(st != ed):
        old = st
        if (st[0] % 2 == 0):
            if st[1] < W - 1:
                st = (st[0], st[1] + 1)
            else:
                st = (st[0]+1, st[1])
        else:
            if st[1] > 0:
                st = (st[0], st[1] - 1)
            else:
                st = (st[0]+1, st[1])
        res.append('%d %d %d %d' % (old[0]+1, old[1]+1, st[0]+1, st[1]+1))
    return res

ans = []
# print (seeds)
seeds = sorted(seeds, key=lambda x:(x[0] * 9999999 + x[1] * (-1 if x[0]%2 == 1 else 1)))
# print (seeds)
for i in range(0, len(seeds)-1, 2):
    st = seeds[i]
    ed = seeds[i+1]
    ans += f(st, ed)
print(len(ans))
print('\n'.join(ans))
### BUGGY CODE ###

n, q = map(int, input().strip().split(' '))
s = input()
for i in range(q):
    l, r = map(int, input().strip().split(' '))
    print(s[l-1:r].count('AC'))

### FIXED CODE ###

n, q = map(int, input().strip().split(' '))
s = input()
ac = []
kazu = 0
for i in range(n-1):
    if s[i:i+2] == 'AC':
        kazu = kazu + 1
        ac.append(kazu)
    else:
        ac.append(kazu)
ac.append(0)
for i in range(q):
    num = 0
    l, r = map(int, input().strip().split(' '))
    print(ac[r-2]-ac[l-2])
### BUGGY CODE ###

import collections

N = int(input())
s = [0] * N
for i in range(N):
    s[i] = input()

c = [0] * N
for i in range(N):
    c[i] = collections.Counter(s[i])

cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        if c[i] == c[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

import collections

N = int(input())
s = [0] * N
for i in range(N):
    s[i] = sorted(input())
    s[i] = " ".join(s[i])

cnt = 0
for i in collections.Counter(s).values():
    cnt += i * (i - 1) // 2
print(cnt)
### BUGGY CODE ###

N = int(input())
A = {}
for i in range(N):
    A[i] = list(map(lambda x: int(x)-1, input().split()))

days = 0
games_amount = 0
for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
        if games*2 >= N:
            break
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
print(days)

### FIXED CODE ###

import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)
### BUGGY CODE ###

import numpy as np
import sys
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4,i4,i4[:],i4[:],i4[:],i4[:])',cache=True)
def main(prev,remain,q,v,w,vq,lq):
    dp = np.zeros((2**prev+1,10**5+1),np.int32)
    for i in range(1,2**prev+1):
        vi = v[i]
        wi = w[i]
        dp[i]=dp[i//2]
        for j in range(wi,10**5+1):
            dp[i][j] = max(dp[i][j],dp[i//2][j-wi]+vi)
    for i in range(q):
        V,L= vq[i],lq[i]
        if V <= 2**prev:
            print(dp[V][L])
        else:
            ans = 0
            for j in range(2**remain):
                cur = V
                curw = 0
                curv = 0
                while cur > 2**prev:
                    if j & 1:
                        curv += v[cur]
                        curw += w[cur]
                    cur //= 2
                    j >>= 1
                if curw <= L:
                    ans = max(ans,dp[cur][L-curw]+curv)
            print(ans)

n = int(readline())
stdin = np.array(read().split(),np.int32)
v = np.zeros(n+1,np.int32)
w = np.zeros(n+1,np.int32)
v[1:] = stdin[:2*n:2]
w[1:] = stdin[1:2*n:2]
q = stdin[2*n]
query = stdin[2*n+1:]
vq = query[::2]
lq = query[1::2]
k = 0
num = 1
while num < n:
    k += 1
    num *= 2
prev = k//2
remain = k-k//2
main(prev,remain,q,v,w,vq,lq)

### FIXED CODE ###

import numpy as np
import sys
from numba import njit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:],i4[:])',cache=True)
def precompute(n,v,w):
    dp = np.zeros((1024,10**5+1),np.int32)
    for i in range(1,min(1024,n+1)):
        vi = v[i]
        wi = w[i]
        p = i//2
        dp[i]=dp[p]
        for j in range(wi,10**5+1):
            dp[i][j] = max(dp[i][j],dp[p][j-wi]+vi)
    return dp

@njit('(i4,i4[:],i4[:],i4[:],i4[:])',cache=True)
def main(n,v,w,vq,lq):
    dp = precompute(n,v,w)
    values = np.empty(1024,np.int32)
    weights = np.empty(1024,np.int32)

    def solve(V,L,values,weights,dp):
        if V < 1024:
            return dp[V][L]
        values[0] = 0
        weights[0] = 0
        p = 0
        while V >= 1024:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j]+ v[V]
                weights[j + (1 << p)] = weights[j] + w[V]
            p += 1
            V >>= 1
        ans = 0
        for i in range(1 << p):
            if weights[i] <= L:
                x = dp[V][L-weights[i]] + values[i]
                ans = max(ans,x)
        return ans
    q = len(vq)
    for i in range(q):
        x = solve(vq[i],lq[i],values,weights,dp)
        print(x)
       
n = int(readline())
stdin = np.array(read().split(),np.int32)
v = np.zeros(n+1,np.int32)
w = np.zeros(n+1,np.int32)
v[1:] = stdin[:2*n:2]
w[1:] = stdin[1:2*n:2]
query = stdin[2*n+1:]
vq = query[::2]
lq = query[1::2]

main(n,v,w,vq,lq)
### BUGGY CODE ###

s=input()
t=input()

len_s=len(s)
len_t=len(t)

DP=[[0 for j in range(len_t+1)] for i in range(len_s+1)]


for i in range(1,len_s+1):
    for j in range(1,len_t+1):
        if s[i-1]==t[j-1]:
            DP[i][j]=DP[i-1][j-1]+1
        else:
            DP[i][j]=max(DP[i-1][j],DP[i][j-1])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=s[x-1]
        x-=1
        y-=1

print(ANS[::-1])

### FIXED CODE ###

s=input()
t=input()

len_s=len(s)
len_t=len(t)

DP=[[0 for j in range(len_t+1)] for i in range(len_s+1)]


for i in range(1,len_s+1):
    for j in range(1,len_t+1):
        if s[i-1]==t[j-1]:
            DP[i][j]=DP[i-1][j-1]+1
        else:
            DP[i][j]=max(DP[i-1][j],DP[i][j-1])
            
        
x,y=len_s,len_t
ANS=""

while x>0 and y>0:
    if x>0 and DP[x-1][y]==DP[x][y]:
        x-=1
    elif y>0 and DP[x][y-1]==DP[x][y]:
        y-=1
    else:
        ANS+=s[x-1]
        x-=1
        y-=1

print(ANS[::-1])
### BUGGY CODE ###

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

pool = []

for Ai in A:
    pool.append(Ai)

for Bi, Ci in BC:
    for _ in range(Bi):
        pool.append(Ci)

pool.sort(key=lambda x: -x)

print(sum(pool[:N]))

### FIXED CODE ###

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


table = {}
for Ai in A:
    table[str(Ai)] = 0
for Bi, Ci in BC:
    table[str(Ci)] = 0
    
for Ai in A:
    table[str(Ai)] += 1

for Bi, Ci in BC:
    table[str(Ci)] += Bi

table2 = [(int(key), value) for key, value in table.items()]
table2.sort(key=lambda x: -x[0])

ans = ans_cnt = 0
for key, value in table2:
    # print("#", key, value, ans_cnt, ans)
    if ans_cnt + value >= N:
        ans += key * (N - ans_cnt)
        break
    else:
        ans_cnt += value
        ans += key * value

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

n = int(input())
temp = 0
while(n!=0):
	temp += n%10
	n= n//10
if temp%9==0:
	print("Yes")
else:
	print("No")	


### FIXED CODE ###

x = sum(list(map(int,input())))

if x%9==0:
	print("Yes")
else:
	print("No")
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
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
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
ab = [LIST() for _ in range(N-1)]

graph = defaultdict(list)

edge = [[0]*N for _ in range(N)]
for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

K = 0
for i in graph:
	K = max(K, len(graph[i]))
color = list(range(1, K+1))
def DFS(i, color_from):  # color_fromからきた色を使わない
	can_use_color = color.copy()
	for node in graph[i]:
		if not edge[i][node]:
			use_color = can_use_color.pop()
			if use_color == color_from:
				use_color = can_use_color.pop()
			edge[i][node] = use_color
			edge[node][i] = use_color
			DFS(node, use_color)

DFS(0, None)

print(K)
for a, b in ab:
	print(edge[a-1][b-1])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
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
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N = INT()
	ab = [LIST() for _ in range(N-1)]

	graph = defaultdict(list)

	# edge = [[0]*N for _ in range(N)]
	edge = defaultdict(int)
	for a, b in ab:
		graph[a-1].append(b-1)
		graph[b-1].append(a-1)

	K = 0
	for v in graph.values():
		K = max(K, len(v))
	color = list(range(1, K+1))

	q = deque()
	q.append((0, None))

	while q:
		i, color_from = q.popleft()
		tmp = -1
		for node in graph[i]:
			str_ = "{},{}".format(i, node)
			if not edge[str_]:
				use_color = color[tmp]
				if use_color == color_from:
					use_color = color[tmp-1]
					tmp -= 1
				tmp -= 1
				edge[str_] = use_color
				edge["{},{}".format(node, i)] = use_color
				q.append((node, use_color))
	print(K)
	for a, b in ab:
		print(edge["{},{}".format(a-1, b-1)])


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

import numpy as np
inp = input()
ACGT = ["", "A", "C", "G", "T"]
sentences = [i+j+k+l+m+n+o+p+q+r+s for i in ACGT for j in ACGT for k in ACGT for l in ACGT for m in ACGT for n in ACGT for o in ACGT for p in ACGT for q in ACGT for r in ACGT for s in ACGT]
length = [len(sent) for sent in sentences if sent in inp]
print(np.max(length))

### FIXED CODE ###

inp = input()
res = 0
for i in range(len(inp)+1):
  for j in range(i+1, len(inp)+1):
    if len([w for w in inp[i:j] if w in ["A", "C", "G", "T"]]) == (j-i):
      res = max(res, j-i)
print(res)
### BUGGY CODE ###

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

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
color = [[-1 for _ in range(N)] for _ in range(N)]
edges = defaultdict(int)

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    numOfEdges[a] += 1
    numOfEdges[b] += 1
    edges[(a, b)] = 0
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        if now < adj:
            edges[(now, adj)] = col + i
        else:
            edges[(adj, now)] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for k, i in edges.items():
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)


### FIXED CODE ###

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

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = defaultdict(int)

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    numOfEdges[a] += 1
    numOfEdges[b] += 1
    edges[(a, b)] = 0
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        if now < adj:
            edges[(now, adj)] = col + i
        else:
            edges[(adj, now)] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for k, i in edges.items():
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)
### BUGGY CODE ###

from sys import stdin
R, G, B, N = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 0
for i in range(3000):
  for j in range(3000):
    tmp = i*R+j*G
    if N >= tmp and (N-tmp)%B == 0:
      ans += 1
print(ans)

### FIXED CODE ###

from sys import stdin
R, G, B, N = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 0
for i in range(3001):
  for j in range(3001):
    tmp = i*R+j*G
    if N >= tmp and (N-tmp)%B == 0:
      ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
x = [0]
for i in range(n):
    s = str(input())
    if s in x:
        n -= 1
    else:
        x.append(s)
print(n)

### FIXED CODE ###

n = int(input())
x = {0}
for i in range(n):
    s = str(input())
    if s in x:
        n -= 1
    else:
        x.add(s)
print(n)
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(0, K + 1):
	for y in range(0, K + 1):
		for z in range(0, K + 1):
			if ((x + y + z) == S):
				count = count + 1
print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(0, K+1):
	if (x > S):
		break
	for y in range(0, min(S-x+1, K+1)):
		if (S-x-y >= 0 and S-x-y <= K):
			count = count + 1

print(count)