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

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    frd=[[0]]
    #print(frd)
    for i in range(m):
        a,b=INTM()
        flg=True
        for k in range(len(frd)):
            if ((a in frd[k])or(b in frd[k])):
                if not(a in frd[k]):
                    frd[k].append(a)
                if not(b in frd[k]):
                    frd[k].append(b)
                flg=False
                break
        if flg:
            frd.append([a,b])
            
                
    #print(frd)
    ans=1
    for i in range(len(frd)):
        ans=max(ans,len(frd[i]))
    
    print(ans)

                
if __name__=='__main__':
    do()

### FIXED CODE ###

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def do():
    n,m=INTM()
    uf=UnionFind(n)
    for i in range(m):
        a,b=INTM()
        uf.union(a-1,b-1)

    ans=0

    for i in range(n):
        ans=max(ans,uf.size(i))
    
    print(ans)
                
if __name__=='__main__':
    do()
### BUGGY CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans=ans*i
print(ans%1000000007)

### FIXED CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans=ans*i
  if ans>1000000007:
    ans=ans%1000000007
print(ans)
### BUGGY CODE ###

def f(n):
  cnt = 0
  for i in range(int(n**1/2 // 1)):
    for j in range(i+1):
      for k in range(j+1):
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n and i==j==k:
          cnt += 1
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n and i==j and i!=k:
          cnt += 3
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n and j==k and j!=i:
          cnt += 3
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n and k==i and k!=j:
          cnt += 3
        if (i+1)**2 + (j+1)**2 + (k+1)**2 + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1) == n and i!=j!=k:
          cnt += 6
  return cnt
      
  
N = int(input())
for i in range(N):
  print(f(i+1))

### FIXED CODE ###

n = int(input())
a = [0]*n
cnt = 0
for i in range(1,100):
  for j in range(1,100):
    for k in range(1,100):
      b = i**2 + j**2 + k**2 + i*j + j*k + k*i
      if b <= n:
        a[b-1] += 1

for i in a:
  print(i)
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    def input(): return sys.stdin.readline().rstrip()

    def bfs():
        inf = 1e18

        dist = [[inf]*w for _ in range(h)]
        dist[xs][ys] = 0
        que = deque([(xs, ys)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            x, y = que.popleft()

            if (x,y) == (xg, yg):
                return dist[x][y]

            for i in range(4):
                nx, ny = x, y
                for _ in range(k):
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if field[nx][ny] == '@': break
                        if dist[nx][ny] <= dist[x][y]: break
                        if dist[nx][ny] > dist[x][y] + 1:
                            dist[nx][ny] = dist[x][y] + 1
                            que.append((nx, ny))
        if dist[xg][yg] == inf:
            return -1


               

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    ans = bfs()
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque

S = input()
N = int(input())
Q = [list(input().split()) for _ in range(N)]

d = deque(S)

for q in Q:
    if q[0] == "1":
        d.reverse()
    elif q[0] == "2":
        if q[1] == "1":
            d.appendleft(q[2])
        else:
            d.append(q[2])
            
print("".join(d))

### FIXED CODE ###

from collections import deque

S = input()
N = int(input())
Q = [list(input().split()) for _ in range(N)]

d = deque(S)

cnt = 0 
for q in Q:
    if q[0] == "1":
        cnt+=1
        #d.reverse()
    elif q[0] == "2":
        if (cnt%2==0 and q[1] == "1") or (cnt%2!=0 and q[1] == "2"):
            d.appendleft(q[2])
        else:
            d.append(q[2])
            
if cnt%2 != 0:
    d.reverse()
print("".join(d))
### BUGGY CODE ###

n = int(input())
s = input()
sum = 0
for i in range(1, n-1):
  h = {"R", "G", "B"} - {s[i-1]}
  sum += s[i:].count(h.pop()) * s[i:].count(h.pop())
  for j in range(i+1, n):
    if(s[i-1] == s[j-1]):
      continue
    k = {"R", "G", "B"} - {s[i-1], s[j-1]}
    k = k.pop()
    if(2*j-i-1 < n):
      if(s[2*j-i-1] == k):
        sum -= 1
print(sum)

### FIXED CODE ###

n = int(input())
s = input()
sum = s.count("R") * s.count("G") * s.count("B")
for i in range(1, n-1):
  for j in range(i+1, n):
    k = 2*j-i-1
    if(k >= n):
      break
    if(len({s[i-1], s[j-1], s[k]}) == 3):
        sum -= 1
print(sum)
### BUGGY CODE ###

from collections import deque
def moores_d(n, s, graph, init_val): 
    d = [init_val] * n
    d[s] = 0
    q = deque([s])
    for _ in range(n):
        m = len(q)
        for _ in range(m):
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = d[vf] + w
                    q.append(vt)
        if not q:
            break
    if q: #閉路の存在
        minus_inf = -float('inf')
        while q:
            vf = q.popleft()
            for vt, w in graph[vf]:
                if d[vt] > d[vf] + w:
                    d[vt] = minus_inf
                    q.append(vt)
    return d

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    graph[a-1].append((b-1, -w))
d = moores_d(n, 0, graph, float('inf'))
print(-d[-1] if d[-1] != -float('inf') else 'inf')


### FIXED CODE ###

n, m = map(int, input().split())

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

init_val = -10 ** 9 * 1000
d = [init_val] * n
d[0] = 0
for _ in range(n):
    updated = False
    for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            updated = True
    if not updated:
        break
if updated: #閉路の存在
     for a, b, w in edges:
        if d[a] != init_val and d[b] < d[a] + w:
            d[b] = d[a] + w
            if b == n - 1:
                print('inf')
                quit()
print(d[n-1])
### BUGGY CODE ###

N = int(input())
S = list(input())
S = S + ['#']
l_sum = []

for i in range(len(S)):
    l_sum.extend([S[0:i].count('#')+S[i:len(S)].count('.')])

print(min(l_sum))


### FIXED CODE ###

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

c_b = 0
c_w = S.count('.')
sum = []

for i in S:
	if i == '.':
		c_w = c_w - 1
	sum.extend([c_b+c_w])
	if i == '#':
		c_b = c_b + 1

print(min(sum))
### BUGGY CODE ###

import math
import numpy
N,M=map(int,input().split())
a=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    tmpc=list(map(int,input().split()))
    c=0
    for j in range(len(tmpc)):
        c+=2**(tmpc[j]-1)
    tmp[1]=c
    a+=[tmp]


dp=[[10**10 for j in range(2**N)] for i in range(M)]
dp[0][0]=0
dp[0][a[0][1]]=a[0][0]


for i in range(1,M):
    dp[i]=dp[i-1]
    for j in range(2**N):
        if dp[i-1][j]<10**10:
            q=j|a[i][1]
            dp[i][q]=min(dp[i-1][j]+a[i][0],dp[i][q])

ans=dp[M-1][2**N-1]
print(ans if ans<10**10 else -1)

### FIXED CODE ###

def main():
    N,M=map(int,input().split())
    L=2**N
    dp=[10**10 for i in range(L)]
    dp[0]=0


    for i in range(M):
        a, _ = map(int, input().split())
        key=sum([2**(int(i)-1) for i in input().split()])
        for j in range(L):
                q=j|key
                dp[q]=min(dp[j]+a,dp[q])


    ans=dp[L-1]
    print(ans if ans<10**10 else -1)

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

n = int(input())
p = list(map(int,input().split()))

cnt = 1
for i in range(1,len(p)):
    if min(p[:i]) >= p[i]:
        cnt+=1
    
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))

cnt = 1
m = p[0]

for i in range(1,len(p)):
    if m >= p[i]:
        cnt+=1
    
    m = min(m,p[i])
    
print(cnt)
### BUGGY CODE ###

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

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(0, k+1):
        for j in range(0, k+1):
                if 0 <= s-i-j <= k:
                        count += 1
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in a:
  ans.append(i)
  ans = ans[::-1]
print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
if n%2==0:
  front = a[::2]
  back = a[1::2][::-1]
else:
  front = a[1::2]
  back = a[::2][::-1]
ans = back+front
print(*ans)
### BUGGY CODE ###

s=input()
n=len(s)
count=0
if n<4:
    print(0)
else:
    for i in reversed(range(2,n)):
        k=int(s[i-2:i+1])
        h=3
        for j in reversed(range(0,i-2)):
            k=k+10**(h)*int(s[j])
            h+=1
            if k%2019==0:
                count+=1
    print(count)

### FIXED CODE ###

import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
b=[0 for i in range(n)]
b[0]=1
for i in range(1,n):
    b[i]=b[i-1]*10%2019
for i in reversed(range(0,n)):
    k+=(b[n-i-1])*int(s[i])%2019
    a[k%2019]+=1        
for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

for id in range(1,n+1):
	ans = a.count(id)
	print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

boss = [0 for _ in range(n)]

for id in a:
	boss[id-1] += 1

for cnt in boss:
	ans = cnt
	print(ans)
### BUGGY CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
for i in range(M):
  t.append(A.count(C[i]))
  temp = A.count(C[i])
  if temp >=2:
    anst += temp*(temp-1)/2

jisyo = dict(zip(C, t))
    
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))

### FIXED CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
table = [0 for i in range(1000000001)]
for i in range(n):
    table[a[i]]+=1
for i in range(n):
    if table[a[i]] != 0 and table[a[i]] != a[i]:
        if table[a[i]] > a[i]:
            ans+=(table[a[i]]-a[i])
        else:
            ans+=table[a[i]]
    table[a[i]] = 0
print(ans)


### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))

count = collections.Counter()

for i in a:
    count[i] += 1

ans = 0
for num,c in count.items():
    if num < c:
        ans += c - num
    elif num > c:
        ans += c
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod_a = [i%(10**9 + 7) for i in a]
res = 0
for i in range(0, len(a)-1):
  for j in range(i+1, len(a)):
    res += (mod_a[i]*mod_a[j])%(10**9 + 7)
print(res%(10**9 + 7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
#mod_a = [i%(10**9 + 7) for i in a]
res = 0
sum_a = sum(a)
b = 0
t = 0
for i in range(0, len(a)-1):
  t = a[i]
  b += a[i]
  res += (sum_a - b)*t%(10**9 + 7)
print(res%(10**9 + 7))
### BUGGY CODE ###

def conbi(n, r):
    bunbo = 1
    bunshi = 1
    if n / 2 < r:
        r = n - r
    while r > 0:
        bunbo *= r
        bunshi *= n
        r -= 1
        n -= 1
    return bunshi // bunbo

def conbi_mod(n, r):
    return conbi(n, r) % (10 ** 9 + 7)
    


H, W, A, B = map(int, input().split())

if B < W / 2:
    not_ans = 0
    total = conbi_mod((H - 1) + (W - 1), H-1)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi((sq1h -1) + (sq1w - 1), (sq1h -1)) * conbi((sq2h - 1) + (sq2w - 1), (sq2h - 1)) % (10 ** 9 + 7)
        not_ans += n
    ans = (total - not_ans) % (10 ** 9 + 7)
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = conbi((sq1h - 1) + (sq1w - 1), (sq1h - 1)) * conbi((sq2h - 1) + (sq2w - 1), (sq2h - 1)) % (10 ** 9 + 7)
        ans += n
    ans = ans % (10 ** 9 + 7)
    print(ans)

### FIXED CODE ###

mod = 10 ** 9 + 7
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append(fact[-1] * i % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def combi_mod(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


H, W, A, B = map(int, input().split())

if B < W / 2:
    not_ans = 0
    total = combi_mod((H - 1) + (W - 1), H-1, mod)
    for i in range(B):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h -1) + (sq1w - 1), (sq1h -1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod) % mod
        not_ans = (not_ans + n) % mod
    ans = (total - not_ans) % mod
    print(ans)
        
else:
    ans = 0
    for i in range(B, W):
        sq1h = H - A
        sq1w = i + 1
        sq2h = A
        sq2w = W - i
        n = combi_mod((sq1h - 1) + (sq1w - 1), (sq1h - 1), mod) * combi_mod((sq2h - 1) + (sq2w - 1), (sq2h - 1), mod)
        ans = (ans + n) % mod
    ans %= mod
    print(ans)
### BUGGY CODE ###

def isallblack(a):
    h=len(a)-2
    w=len(a[0])-2
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='.':
                return False
    return True

H,W=map(int,input().split())
a=['.'*(W+2)]
for i in range(H):
    a.append('.'+input()+'.')
a.append('.'*(W+2))

c=[[False for j in range(W+2)] for i in range(H+2)]
cnt=0

while not isallblack(a):
    for i in range(1,H+1):
        for j in range(1,W+1):
            c[i][j]=(a[i][j]=='#' or a[i-1][j]=='#' or a[i+1][j]=='#' or a[i][j-1]=='#' or a[i][j+1]=='#')
    for i in range(1,H+1):
        for j in range(1,W+1):
            if c[i][j]:
                a[i]=a[i][:j]+'#'+a[i][j+1:]
    cnt+=1

print(cnt)

### FIXED CODE ###

from collections import deque

class Grid():
    def __init__(self,i,j,isblack):
        self.i=i
        self.j=j
        self.isblack=isblack
        self.distance=0

H,W=map(int,input().split())

g=[]
for i in range(H):
    Ai=input()
    gi=[]    
    for j in range(W):
        gi.append(Grid(i,j,Ai[j]=='#'))
    g.append(gi)

d=deque()

# 黒マスのreachedをTrueにし，dequeに入れる
for row in g:
    for grid in row:
        if grid.isblack:
            d.append(grid)

while d:
    tg=d.popleft()
    i=tg.i
    j=tg.j
    if i>0 and not g[i-1][j].isblack:
        g[i-1][j].isblack=True
        g[i-1][j].distance=tg.distance+1
        d.append(g[i-1][j])
    if i<H-1 and not g[i+1][j].isblack:
        g[i+1][j].isblack=True
        g[i+1][j].distance=tg.distance+1
        d.append(g[i+1][j])
    if j>0 and not g[i][j-1].isblack:
        g[i][j-1].isblack=True
        g[i][j-1].distance=tg.distance+1
        d.append(g[i][j-1])
    if j<W-1 and not g[i][j+1].isblack:
        g[i][j+1].isblack=True
        g[i][j+1].distance=tg.distance+1
        d.append(g[i][j+1])

'''
for row in g:
    for grid in row:
#        print(grid.distance,end=' ')
#    print()
'''

print(max([max([grid.distance for grid in row]) for row in g]))
### BUGGY CODE ###



def rec(a, s, e, dp, ss):
    if dp[s][e] > 0:
        return dp[s][e]

    if e - s == 1:
        dp[s][e] = 0
        return 0
    
    cur_min = float('inf')
    for i in range(s + 1, e):
        lc = rec(a, s, i, dp, ss)
        rc = rec(a, i, e, dp, ss)
        test = lc + rc + ss[s][e]
        if test < cur_min:
            cur_min = test
    dp[s][e] = cur_min
    return cur_min


def submit():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    ss = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(i, n + 1):
            ss[i][j] = sum(a[i:j])
    
    print(rec(a, 0, n, dp, ss))


submit()

### FIXED CODE ###



def rec(a, s, e, dp, ss):
    if dp[s][e] > 0:
        return dp[s][e]

    if e - s == 1:
        dp[s][e] = 0
        return 0
    
    cur_min = float('inf')
    for i in range(s + 1, e):
        lc = rec(a, s, i, dp, ss)
        rc = rec(a, i, e, dp, ss)
        test = lc + rc + ss[s][e]
        if test < cur_min:
            cur_min = test
    dp[s][e] = cur_min
    return cur_min


def submit():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    ss = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(i, n + 1):
            ss[i][j] = sum(a[i:j])
    
    print(rec(a, 0, n, dp, ss))


submit()
### BUGGY CODE ###

from collections import deque
def bfs(graph, N, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        # do_something(node)
        color = 1
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                while color in colors[node].values():
                    color += 1
                colors[node][n] = color
                colors[n][node] = color
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
colors = bfs(graph, N, 0)
print(max(counts))
for i, j in inputs:
    print(colors[i][j])

### FIXED CODE ###

from collections import deque
def color_available(unavailable, K):
    idx = 0
    L = len(unavailable)
    unavailable = sorted(unavailable)
    for color in range(K):
        if idx < L and color == unavailable[idx]:
            idx += 1
        else:
            yield color

def bfs(graph, N, K, start):
    colors = [dict() for _ in range(N)]
    visited = [0] * N
    visited[start] = 1
    que = deque([start])
    while que:
        node = que.popleft()
        gen = color_available(colors[node].values(), K)
        color = 1
        for n in graph[node]:
            if not visited[n]:
                visited[n] = 1
                color = next(gen)
                colors[node][n] = color
                colors[n][node] = color
                que.append(n)
    return colors

N = int(input())
graph = [[] for _ in range(N)]
inputs = tuple(tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(N - 1))
counts = [0] * N
for i, j in inputs:
    graph[i].append(j)
    graph[j].append(i)
    counts[i] += 1
    counts[j] += 1
K = max(counts)
colors = bfs(graph, N, K, 0)
print(K)
for i, j in inputs:
    print(colors[i][j] + 1)
### BUGGY CODE ###

n,h = map(int,input().split())
a_list = []
b_list = []
use_b_list = []
for i in range(n):
  a,b = map(int,input().split())
  a_list.append(a)
  b_list.append(b)
import math
for b in b_list:
  if b > max(a_list):
    use_b_list.append(b)
use_b_list.sort(reverse = True)    
count = 0
if sum(use_b_list) >= h:
  for i in range(len(use_b_list)):
    h -= use_b_list[i]
    count += 1
    if h <= 0:
      break
  print(count)
else:
  h -= sum(use_b_list)
  print(len(use_b_list) + int(math.ceil(h/max(a_list))))

### FIXED CODE ###

n,h = map(int,input().split())
a_list = []
b_list = []
use_b_list = []
for i in range(n):
  a,b = map(int,input().split())
  a_list.append(a)
  b_list.append(b)
use_a = max(a_list)
import math
for b in b_list:
  if b > use_a:
    use_b_list.append(b)
use_b_list.sort(reverse = True)    
count = 0
if sum(use_b_list) >= h:
  for i in range(len(use_b_list)):
    h -= use_b_list[i]
    count += 1
    if h <= 0:
      break
  print(count)
else:
  h -= sum(use_b_list)
  print(len(use_b_list) + int(math.ceil(h/max(a_list))))
### BUGGY CODE ###

n,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(w):
        dp[i][j]=dp[i-1][j]
    for j in range(W-w+1):
        dp[i][j+w]=max(dp[i-1][j+w],dp[i-1][j]+v)
print(max(dp[-1]))


### FIXED CODE ###

n,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
    w,v=map(int,input().split())
    for j in range(w):
        dp[i][j]=dp[i-1][j]
    for j in range(W-w+1):
        dp[i][j+w]=max(dp[i-1][j+w],dp[i-1][j]+v)
print(max(dp[-1]))