Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.
Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

-----Constraints-----
 -  2 \le N \le 10^5
 -  1 \le a_i \lt b_i \le N
 - All values in input are integers.
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

-----Output-----
Print N lines.
The first line should contain K, the number of colors used.
The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

-----Sample Input-----
3
1 2
2 3

-----Sample Output-----
2
1
2


Difficulty: interview

Starter code:

Solutions:
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()))
from collections import deque

class Graph():
    def __init__(self, v):
        from heapq import heappop, heappush
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, edge):
        self.graph[start].append((end, edge))
        self.graph[end].append((start, edge))

def do():
    n=INT()
    g=Graph(n)
    for i in range(n-1):
        a,b=INTM()
        a-=1
        b-=1
        g.addEdge(a,b,i)

    
    que=deque()
    check=[True]*n
    clrs=[0]*(n-1)
    que.append([0,0])
    check[0]=False
    while que:
        clr=1
        now,clr_f=que.popleft()
        if clr_f==1:
            clr=2
        for next,i in g.graph[now]:
            if check[next]:
                check[next]=False
                que.append([next,clr])
                clrs[i]=clr
                clr+=1
                if clr==clr_f:
                    clr+=1
    
    print(max(clrs))
    for i in range(n-1):
        print(clrs[i])








def __starting_point():
    do()
__starting_point()

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for i,(a,b) in enumerate(AB):
    a,b = a-1,b-1
    es[a].append((b,i))
    es[b].append((a,i))

ans = [None] * (N-1)

def dfs(v,p=-1,c=-1):
    nc = 1
    for to,e in es[v]:
        if to==p: continue
        if nc==c: nc += 1
        ans[e] = nc
        dfs(to,v,nc)
        nc += 1
dfs(0)

print(max(ans))
print(*ans, sep='\n')

N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
K = -1
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        K = max(c, K)
        color[y] = c
        c += 1

ans = []

for a, b in AB:
    if parent[a] == b:
        ans.append(color[a])
    else:
        ans.append(color[b])

print(K)
for i in ans:
  print(i)


from collections import deque,defaultdict
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a,b=list(map(int, input().split()))
    edges[a-1].append([b-1,i])
    edges[b-1].append([a-1,i])
c = 1
col = [0]*(n-1)
visited = [0]*(n-1)
que=deque()
for v in edges[0]:
    que.append(v)
    col[v[1]]=c
    visited[v[1]]=1
    c+=1
while que:
    v=que.popleft()
    c = 1
    used = set()
    for i in edges[v[0]]:
        if(visited[i[1]]):
            used.add(col[i[1]])
    for next_v in edges[v[0]]:
        if(not visited[next_v[1]]):
            if(c in used):
                c+=1
            col[next_v[1]] = c
            used.add(c)
            c+=1
            visited[next_v[1]] = 1
            que.append(next_v)
print((max(col)))
for i in col:
    print(i)


from collections import deque

def main():
  n = int(input())
  graph=[[] for _ in range(n+1)]
  for i in range(1,n):
    a,b = map(int, input().split())
    d1 = {"id":i,"to":b}
    d2 = {"id":i,"to":a}
    graph[a].append(d1)
    graph[b].append(d2)
  
  k = 0
  root = 1
  for i in range(1, n+1):
    if k < len(graph[i]):
      root = i
      k = max(k, len(graph[i]))
  print(k)
  q=deque([root])
  color=[[] for _ in range(n+1)]
  reached=[False]*(n+1)
  ans=[0]*(n)
  while q:
    current = q.popleft()
    reached[current] = True
    temp = 1
    for dic in graph[current]:
      id = dic["id"]
      next = dic["to"]
      if reached[next]:
        continue
      while temp in color[current]:
        temp += 1
      color[next].append(temp)
      ans[id] = temp
      temp += 1
      q.append(next)
  for i in ans[1:]:
    print(i)
      
def __starting_point():
  main()
__starting_point()

from collections import deque
n=int(input())
ab=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a].append([b,i])
que=deque()
que.append(1)
visited=[0]*(n)
ans=[0]*(n-1)
while que:
    x=que.popleft()
    k=1
    for j in ab[x]:
        if visited[x-1]!=k:
            ans[j[1]]+=k
            visited[j[0]-1]+=k
            k+=1
            que.append(j[0])
        else:
            ans[j[1]]+=(k+1)
            visited[j[0]-1]+=(k+1)
            k+=2
            que.append(j[0])
print(max(ans))
for l in ans:
    print(l)

import sys
from collections import deque

n = int(sys.stdin.readline())
G = [[] for _ in range(n+1)]
G_order = []
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, sys.stdin.readline().split())
    G[a].append(b)
    G_order.append(b)

que = deque([0])
C = [0]*(n+1)
while que:
    nw = que.popleft()
    c = 1
    for nx in G[nw]:
        if c==C[nw]:
            c+=1
        C[nx] = c
        c += 1
        que.append(nx)

print(max(C))
for i in G_order:
    print(C[i])

from collections import deque
n = int(input())
a = [[] for i in range(n)]
e = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b].append(c)
  e.append(c)
col = [0 for i in range(n)]
v = deque([0])

while v:
  d = v.popleft()
  k = 1
  for i in a[d]:
    if col[d] == k:
      k += 1
    col[i] = k
    v.append(i)
    k += 1
print (max(col))
for i in e:
  print(col[i])

from collections import deque, defaultdict
N = int(input())
d = defaultdict(list)
m = dict()
ls = []
for i in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)
    ls.append((a, b))

K = 0
for i in range(N):
    d[i+1].sort()
    K = max(K, len(d[i+1]))
print(K)

q = deque([])
q.append((1, 0))
visited = [0 for i in range(N+1)]
visited[1] = 1
while q:
    l, r = q.popleft()
    flag = 0
    cur = 1
    for i, x in enumerate(d[l], start=1):
        if visited[x] == 1:
            continue
        if flag == 0:
            if cur == r:
                q.append((x, cur+1))
                m[(l, x)] = cur+1
                m[(x, l)] = cur+1
                cur += 2
                visited[x] = 1
                flag = 1
                continue
            m[(l, x)] = cur
            m[(x, l)] = cur
            q.append((x, cur))
            cur += 1
            visited[x] = 1
        else:
            q.append((x, cur))
            m[(l, x)] = cur
            m[(x, l)] = cur
            cur += 1
            visited[x] = 1
for i in range(N-1):
    a, b = ls[i]
    print(m[(a, b)])

#create date: 2020-07-05 13:34

import sys
stdin = sys.stdin
from collections import deque

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    g = [list() for _ in range(n)]
    to = list()
    for i in range(n-1):
        a, b = na()
        a -= 1; b -= 1
        g[a].append(b)
        to.append(b)
    l = [-1] * n
    l[0] = 10**10
    q = deque([0])
    while q:
        v = q.popleft()
        vcolor = l[v]
        for i, w in enumerate(g[v]):
            q.append(w)
            if i < vcolor:
                l[w] = i
            else:
                l[w] = i + 1

    print(max(l[1:])+1)
    for i in to:
        print(l[i]+1)



def __starting_point():
    main()
__starting_point()

import sys
sys.setrecursionlimit(10**6)

n = int(input())
t = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int,input().split())
    t[a].append((b,i))
    t[b].append((a,i))
num = max([len(tmp) for tmp in t])
print(num)

ans = [-1]*(n-1)

def dfs(n, before, bcol):
    col = 1
    for i, j in t[n]:
        if i == before:
            continue
        if col == bcol:
            col += 1
        ans[j] = col
        dfs(i, n, col)
        col += 1

dfs(1, 0, -1)
for i in range(n-1):
    print(ans[i])

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 = list(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 list(edges.items()):
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)


from collections import deque
n=int(input())
g=[[] for _ in range(n+1)]
e=[]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    e.append(b-1)

q=deque([0])

color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1

        color[x]=c
        c+=1
        q.append(x)

print(max(color))
for i in e:
    print(color[i])

from collections import deque

def main():
    n = int(input())
    adj = [[]for i in range(n+1)]
    ab = [list(map(int, input().split())) for i in range(n-1)]
    for a, b in ab:
        adj[a].append(b)
        adj[b].append(a)
    # dequeを使ったキューによるBFS
    # 子をindexで、親ノードを要素で
    # 今回は彩色のためにどんな順番でpopされたかも保持しておく
    order  = []
    parent = [None] * (n+1)
    q = deque([1])
    while q:
        par = q.popleft()
        order.append(par)
        for chl in adj[par]:
            if chl == parent[par]:
                continue
            parent[chl] = par
            q.append(chl)
    # 彩色
    # 親と同じにならないように若い番号を割り当てて行く
    cl = [None] * (n+1)
    for par in order:
        # 親の色
        pc = cl[par]
        # 彩色は1以上k以下
        color = 1
        for chl in adj[par]:
            # 隣接リストの親は無視
            if chl == parent[par]:
                continue
            # 親の色と同じなら色を変える
            if pc == color:
                color += 1
            # カラーリストに子indexにcolorを入れる
            cl[chl] = color
            #　他の子は色を変える必要がある
            color += 1
    # 木グラフなので単純に次数最大で考えて問題ない
    g = max([len(i) for i in adj]) 
    print(g)   
    for a, b in ab:
        # 親子関係が逆転しない出力ならこれでいいがそうとも限らない 
        if parent[a] != b:
            print(cl[b])
        else:
            print(cl[a])    
    
def __starting_point():
    main()
__starting_point()

from collections import deque

n=int(input())
r=[[] for _ in range(n)]
kumi=[]
for _ in range(n-1):
  s=list(map(int,input().split()))
  kumi.append(str(s[0]-1)+'+'+str(s[1]-1))
  r[s[0]-1].append(s[1]-1)
  r[s[1]-1].append(s[0]-1)
  
  
ans=0
for i in range(n):
  ans=max(len(r[i]),ans)

print(ans)

ans_iro=[[] for _ in range(n)]

iro=[-1 for _ in range(n)]
iro[0]=1
ch=1
d=[]
di={}
for i in r[0]:
  iro[i]=ch
  di[str(min(0,i))+'+'+str(max(0,i))]=ch
  ch+=1
  d.append(i)
  
  

d=deque(d)



while d:
  v=d.popleft()
  ch=1
  for i in r[v]:
    if iro[i]==-1:
      if ch==iro[v]:
        ch+=1
        iro[i]=ch
        di[str(min(v,i))+'+'+str(max(v,i))]=ch
        ch+=1
      else:
        iro[i]=ch
        di[str(min(v,i))+'+'+str(max(v,i))]=ch
        ch+=1
        
      d.append(i)
      
for g in kumi:
  print((di[g]))
      

  




import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
Edges = []
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    Edges.append((a-1, b-1))

Col = 0
for n in range(N):
    Col = max(Col, len(graph[n]))

Color = dict()
checked = [-1]*N
q = [0]
checked[0] = Col+1
while q:
    qq = []
    for p in q:
        c = checked[p]
        t = 0
        for np in graph[p]:
            if checked[np] == -1:
                if t == c:
                    t += 1
                checked[np] = t
                Color[(p, np)] = t
                Color[(np, p)] = t
                t += 1
                qq.append(np)
    q = qq

print(Col)
for a, b in Edges:
    print(Color[(a, b)]+1)

import sys
sys.setrecursionlimit(10**8)

def dfs(v,c):
  now = 1
  for u,i in edge[v]:
    if color[i]==0:
      if now==c:
        now += 1
      color[i] = now 
      dfs(u,now)
      now += 1
  return 0

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append([b-1,i])
  edge[b-1].append([a-1,i])
color = [0]*(N-1)
dfs(0,1<<30)
print(max(color))
print(*color, sep='\n')

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = [int(_) - 1 for _ in input().split()]
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = [0] * (N - 1)
colors_num = max([len(_) for _ in edge])
colors = list(range(colors_num))


def dfs(v, pv, pc):
    valid_colors = [c for c in colors if c != pc]
    childs = [c for c in edge[v] if c[0] != pv]
    for ((cv, ci), color) in zip(childs, valid_colors):
        ans[ci] = color + 1
        dfs(cv, v, color)


dfs(0, -1, -1)
print(colors_num)
print((*ans))


from sys import stdin

def getval():
    n = int(input())
    e = [[i] + list(map(int,stdin.readline().split())) for i in range(n-1)]
    return n,e

def main(n,e):
    tree = [[] for i in range(n)]
    ans = [0 for i in range(n-1)]
    for i in e:
        tree[i[1]-1].append([i[2]-1,i[0]])
    tree[0].append(0)
    k = 1
    q = [0]
    while q:
        n = 0
        idx = q.pop(0)
        for i in range(len(tree[idx])-1):
            n += 1
            if n==tree[idx][-1]:
                n += 1
            ans[tree[idx][i][-1]] = n
            tree[tree[idx][i][0]].append(n)
            q.append(tree[idx][i][0])
        k = max(k,n)

    print(k)
    for i in ans:
        print(i)
            
            
def __starting_point():
    n,e = getval()
    main(n,e)
__starting_point()

import sys
sys.setrecursionlimit(10**5)
n = int(input())
ab = [list(map(int,input().split()))for _ in range(n-1)]

graph = [[] for _ in range(n+1)]
ans = [0]*(n-1)
for i in range(n-1):
    graph[ab[i][0]].append((ab[i][1],i))
    graph[ab[i][1]].append((ab[i][0],i))

visit = [False]*(n+1)
def dfs(p,c):
    color = 1
    visit[p] = True
    for n,i in graph[p]:
        if visit[n] == False:
            if color == c:
                color += 1
            ans[i] = color
            dfs(n,color)
            color += 1

dfs(1,0)
print((max(ans)))
for t in ans:
    print(t)


n=int(input())
e=[[] for i in range(n)]
for i in range(n-1):
  inp=list(map(int,input().split()))
  e[inp[0]-1].append((inp[1]-1,i))
  e[inp[1]-1].append((inp[0]-1,i))

col=[0 for i in range(n-1)]
fl=[0 for i in range(n)]
s=[[0,0]]
mc=0
while len(s):
  ns=[]
  for i in s:
    fl[i[0]]=1
    cc=1
    for j in e[i[0]]:
      if not(fl[j[0]]):
        if cc==i[1]:
          cc+=1
        col[j[1]]=cc
        mc=max(mc,cc)
        ns.append([j[0],cc])
        cc+=1
  s=ns

print(mc)
for i in col:
  print(i)


import sys

sys.setrecursionlimit(100000)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    ID = [dict() for _ in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
        ID[a][b] = i
        ID[b][a] = i
    m = max(len(g) for g in G)
    ans = [0] * (n - 1)
    def bfs(a, pre = -1, pre_c = -1):
        color = 1
        for b in G[a]:
            if b == pre: continue
            if color == pre_c: color += 1
            ans[ID[a][b]] = color
            bfs(b, a, color)
            color += 1

    bfs(0)
    print(m)
    [print(a) for a in ans]
      
def __starting_point():
    main()

__starting_point()

N = int(input())

ip = []
hen = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    ip.append([a, b])
    hen[a].append(b)

p = [-1]*N

for i in range(N):
    x = 0
    for j, h in enumerate(hen[i]):
        if p[i] == j:
            x += 1
        p[h] = j+x

print(max(p)+1)
for i in range(N-1):
    print(p[ip[i][1]]+1)

from collections import deque
n=int(input())
tree=[[] for _ in range(n+1)]
for i in range(1,n):
  a,b=map(int,input().split())
  tree[a].append([b,i])
  tree[b].append([a,i])
queue=deque([[1,0]])
ans=[0]*(n+1)
ans[1]=1
visited=[0]*(n+1)

while queue:
  v,c=queue.popleft()
  color=1
  for nv,i in tree[v]:
    if c==color:
      color+=1
    if visited[i]==1:
      continue
    visited[i]=1
    queue.append([nv,color])
    ans[i]=color
    color+=1
print(max(ans))
for i in range(1,n):
  print(ans[i])

def __starting_point():
    import sys
    from collections import deque
    input = sys.stdin.readline
    N = int(input())
    edges = [[] for _ in range(N)]
    for i in range(N-1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        edges[a].append((b,i))
        edges[b].append((a,i))

    color = [None]*(N-1)
    SIZE = 1
    q = deque([(0,None)])
    while q:
        v, prev_color = q.popleft()
        c = 1
        for w, i in edges[v]:
            if not color[i]:
                if c == prev_color:
                    c += 1
                color[i] = c
                c += 1
                q.append((w,color[i]))
        SIZE = max(SIZE, c-1)
    print(SIZE)
    for n in range(N-1):
        print(color[n])
__starting_point()

#!/usr/bin/env python
# coding: utf-8

# In[8]:


import sys
sys.setrecursionlimit(10**9)


# In[10]:


n = int(input())
ab = []
t = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = [int(x)-1 for x in input().split()]
    t[a].append(b)
    t[b].append(a)
    ab.append((min(a,b),max(a,b)))


# In[11]:


k = max(list(map(len,t)))
d = {}
def dfs(pre,cur,col):
    cn = 1 if col != 1 else 2
    for i in t[cur]:
        if i == pre:
            continue
        d[(min(i,cur),max(i,cur))] = cn
        dfs(cur,i,cn)
        cn += 1
        if col == cn:
            cn += 1
dfs(0,0,0)
print(k)
for i in ab:
    print((d[i]))


# In[ ]:






f=lambda:map(int,input().split())
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=f()
  g[a-1]+=[(b-1,i)]
  g[b-1]+=[(a-1,i)]
l=[0]*(n-1)
u=[0]*n
q=[(0,0)]
while q:
  v,s=q.pop()
  u[v]=1
  t=1
  for c,i in g[v]:
    if u[c]: continue
    if t==s: t+=1
    l[i]=t
    q+=[(c,t)]
    t+=1
print(max(l))
for i in l: print(i)

from collections import deque, defaultdict
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
d = [0] * (N + 1)
G = [[] for _ in range(N + 1)]
for a, b in ab:
    d[a] += 1
    d[b] += 1
    G[a].append(b)
    G[b].append(a)
print((max(d)))

color = defaultdict(int)
q = deque([[1, 0]])
seen = [0] * (N + 1)
while q:
    v, c = q.popleft()
    seen[v] = 1
    tem = 1
    for u in G[v]:
        if seen[u]:
            continue
        if tem == c:
            tem += 1
        q.append([u, tem])
        i, j = min(v, u), max(v, u)
        color[(i, j)] = tem
        tem += 1

for a, b in ab:
    i, j = min(a, b), max(a, b)
    print((color[(i, j)]))



from collections import deque
def resolve():
    N = int(input())
    G = [[] for _ in range(N)]
    nextV = []

    for _ in range(N - 1):
        a, b = [int(x) - 1 for x in input().split()]
        G[a].append(b)
        nextV.append(b)

    q = deque()
    q.append(0)
    color = [0] * N
    while q:
        v = q.popleft()
        parentC = color[v]
        c = 1
        for to in G[v]:
            if c == parentC:  # 親と同じ色だったら次の色を使用
                c += 1
            color[to] = c
            c += 1
            q.append(to)

    print((max(color)))
    for b in nextV:
        print((color[b]))


def __starting_point():
    resolve()

__starting_point()

from collections import deque,defaultdict
n = int(input())
data = [[] for _ in range(n)]
sides = []
for _ in range(n-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    data[a].append(b)
    data[b].append(a)
    sides.append((a,b))
I = defaultdict(lambda:0)
cs = [0]*n
used = [0]*n
q = deque([0])
used[0]=1
k = 0
while q:
    u = q.popleft()
    if k < len(data[u]):
        k = len(data[u])
    cur = 1
    for v in data[u]:
        if used[v]:continue
        if cur==cs[u]:cur+=1
        cs[v] = cur
        I[(u,v)] = cur
        I[(v,u)] = cur
        cur += 1
        used[v] = 1
        q.append(v)
print(k)
for i,j in sides:
    print(I[(i,j)])

N = int(input())
inp = []
for k in range(N-1):
  a, b = list(map(int, input().split()))
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False

from bisect import insort


ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
for item in inp:
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print((ans[k]))


import sys
sys.setrecursionlimit(10**9)

n=int(input())
to=[[] for i in range(n)]
edge={}
color=[0]*(n-1)
for i in range(1,n):
  a,b=map(int,input().split())
  a-=1
  b-=1
  to[a].append(b)
  to[b].append(a)
  edge[(a,b)]=edge[(b,a)]=i
def dfs(n,b=-1,bc=-1):
  to_n=to[n]
  k=1
  for i in range(len(to_n)):
    if to_n[i]==b:
      continue
    if k==bc:
      k+=1
    color[edge[(n,to_n[i])]-1]=k
    dfs(to_n[i],n,k)
    k+=1
dfs(0)
print(max(color))
for i in range(n-1):
  print(color[i])

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N = NI()
    edges = [NLI() for _ in range(N-1)]
    graph = [[] for _ in range(N+1)]
    edge_dict = {}
    for i, edge in enumerate(edges):
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])
        edge_dict[(edge[0], edge[1])] = i+1

    queue = deque()
    queue.append(1)
    seen = [0]*(N+1)
    colors = [-1] * N
    colors[1] = 1
    now_colors = deque()
    now_colors.append(-1)
    while queue:
        now = queue.popleft()
        now_color = now_colors.popleft()
        seen[now] = 1
        nexts = graph[now]
        color = 1
        for goto in nexts:
            if seen[goto] == 0:
                a, b = min(now, goto), max(now, goto)
                if color == now_color:
                    color += 1
                colors[edge_dict[(a, b)]] = color
                queue.append(goto)
                now_colors.append(color)
                color += 1
    print(max(colors))
    for i in range(1, N):
        print(colors[i])



def __starting_point():
    main()
__starting_point()

from collections import deque
n = int(input())
edges_ls = [[0,0] for _ in range(n-1)]
edges_d = {}
ver_ls = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges_d[(a,b)] = i
    edges_d[(b,a)] = i
    edges_ls[i] = [a,b]
    ver_ls[a].append(b)
    ver_ls[b].append(a)
n_color = 0
for ver in ver_ls:
    n_color = max(n_color,len(ver))
def next_color(color):
    return (color+1)%n_color

edge_color = [0] * (n-1)
q = deque()
color_now = 0
for ver in ver_ls[0]:
    q.append([0,ver,color_now])
    edge_color[edges_d[(0,ver)]] = color_now
    color_now = next_color(color_now)
done_ls = [0] * n
done_ls[0] = 1

while q:
    From, to, color_now = q.popleft()
    # verはtoからの行先
    for ver in ver_ls[to]:
        if not done_ls[ver]:
            q.append([to,ver,next_color(color_now)])
            edge_color[edges_d[(to,ver)]] = next_color(color_now)
            color_now = next_color(color_now)
    done_ls[to] = 1

print(n_color)
for color in edge_color:
    print(color+1)

N = int(input())

ans = [0] * (N-1)
to = [[] for i in range(N-1)]
used = [0] * N

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

for i in range(N-1):
    unable = used[i]
    c = 1
    for j, id in to[i]:
        if c == unable:
            c += 1
        ans[id] = c
        used[j] = c
        c += 1

print(max(used))
for i in range(N-1):
    print(ans[i])

import sys
from collections import defaultdict, deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

g = [[] for _ in range(N)]
deg = [0] * N
ab = defaultdict(int)

for _ in range(N - 1):
    a, b = list(map(int1, readline().split()))
    g[a].append(b)
    g[b].append(a)
    deg[a] += 1
    deg[b] += 1
    ab[(a, b)] = -1

color = [-1] * N

print((max(deg)))

C = [0] * N
C[0] = -1

que = deque([0])

while len(que) != 0:
    idx = que.popleft()
    tmp = 1
    for i in g[idx]:
        if C[i] != 0:
            continue
        a, b = idx, i
        if tmp == C[idx]:
            tmp += 1
        ab[(a, b)] = tmp
        C[i] = tmp
        que.append(i)
        tmp += 1

for v in list(ab.values()):
    print(v)


from collections import deque
n = int(input())
a = [[] for i in range(n)]
e = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b].append(c)
  e.append(c)
col = [0 for i in range(n)]
v = deque([0])
 
while v:
  d = v.popleft()
  k = 1
  for i in a[d]:
    if col[d] == k:
      k += 1
    col[i] = k
    v.append(i)
    k += 1
print (max(col))
for i in e:
  print(col[i])

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return list(map(int,input().split()))
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()

#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
a_b = []
k=0
for i in range(n-1):
    a,b = MI()
    a_b.append(str(a)+" "+str(b))
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
for i in range(n+1):
    k = max(len(graph[i]),k)
d = deque()
d.append(1)
ans = dict()
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      prev_col[i] = cnt
      ans[str(min(i,v))+" "+str(max(i,v))]=cnt
      d.append(i)
print(k)
for key in a_b:
    print((ans[key]))


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

def coloring(n, previous, col): #頂点nにpreviousから色colで辿ってきた。
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col #やってきた頂点との間における色
		else:
			if cnt == col:
				cnt += 1
			color[(x, n)] = cnt
			color[(n, x)] = cnt
			coloring(x, n, cnt)
			cnt += 1

coloring(0, -1, 0)

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return list(map(t, sysread().split()))
def mapread(t = int):
    return list(map(t, read().split()))

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    num = 1
    for idx, n in to[c]:
        if cols[idx]:continue
        for i in range(num, max_counts+1):
            if not i in colors:
                num = i
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)

    #print(a ^ b)
def __starting_point():
    run()

__starting_point()

from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=list(map(int,input().split()))
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print((color[b]))

def __starting_point():
    n,nList,edges=readinput()
    main(n,nList,edges)

__starting_point()

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)

n=int(input())
e=[[] for i in range(1+n)]
ei={}
for i in range(n-1):
    """#weighted->erase_,__,___=map(int,input().split())
    e[_].append((__,___))
    e[__].append((_,___))
    """
    _,__=map(int,input().split())
    e[_].append(__)
    e[__].append(_)
    ei[_,__]=i
    ei[__,_]=i

    """
"""#weighted->erase
M=max([len(x)for x in e])
res=[0]*(n-1)
from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
Ms=[1]*(1+n)
dq.append(1)
while dq:
    now=dq.popleft()
    for ne in e[now]:
        ind=ei[ne,now]
        if res[ind]==0:
            res[ind]=Ms[now]
            Ms[now]=Ms[now]%M+1
            Ms[ne]=Ms[now]
            dq.append(ne)
print(M)
print(*res,sep='\n')

from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

N  = int(input())
Gb = [ [] for _ in range(N) ]
Gu = [ [] for _ in range(N) ]
Es = {}

for n in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())

    Es[f'{a:06}{b:06}'] = None

    Gb[a].append(b)
    Gb[b].append(a)
    Gu[a].append(b)

colors = list(range(max(map(len, Gb))))

def dfs(base_node, edge_color):
    nonlocal Es

    valid_colors = filter(lambda color: color != edge_color, colors)

    for child_node, color in zip(Gu[base_node], valid_colors):
        Es[f'{base_node:06}{child_node:06}'] = color + 1

        dfs(child_node, color)

print(len(colors))

dfs(0, None)

for color in Es.values():
    print(color)

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
    a,b = na()
    g[a-1].append((b-1,i))

ans = [-1]*(n-1)
m = [0]*n

for i in range(n):
    k = 1
    for c,j in g[i]:
        if m[i] == k: k += 1
        m[c] = k
        ans[j] = k
        k+=1

print(max(m))
print('\n'.join([str(u) for u in ans]))

import sys
from collections import deque
N = int(input())
E = [tuple(map(lambda x: int(x) - 1, sys.stdin.readline().split())) for _ in range(N - 1)]
G = [[] for _ in range(N)]
for a, b in E:
    G[a].append(b)

colornum = len(G[0])
colors = [{} for _ in range(N)]
todo = deque()
for i, p in enumerate(G[0]):
    colors[0][p] = i
    todo.append((0, p))

while todo:
    pp, p = todo.popleft()
    colornum = max(colornum, len(G[p]) + 1)
    c = colors[pp][p]
    for np in G[p]:
        c = (c + 1) % colornum
        colors[p][np] = c
        todo.append((p, np))

print(colornum)
for a, b in E:
    print(colors[a][b] + 1)

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print((color[(a-1, b-1)]))


N = int(input())
from collections import deque
inp = []
for k in range(N-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b-1, a-1
  else:
    a, b = a-1, b-1
  inp.append((a, b, k))
inp.sort(key = lambda x: x[0])
inp = deque(inp)
mark = [[] for _ in range(N)]
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False

from bisect import insort
ans = [0 for _ in range(N-1)]
now = 0
cnt = 0
while inp:
  item = inp.popleft()
  cnt += 1
  if now < item[0]:
    now = item[0]
    cnt = 1
  while binary_search(mark[item[0]], cnt) or binary_search(mark[item[1]], cnt):
    cnt += 1
  insort(mark[item[1]], cnt)
  ans[item[2]] = cnt
color = max(ans)
print(color)
for k in range(N-1):
  print(ans[k])

from collections import defaultdict

N = int(input())
P = [[] for _ in range(N)]
AB = defaultdict(int)

for _ in range(N-1):
  a, b = [int(x)-1 for x in input().split()]
  P[a].append(b)
  P[b].append(a)
  AB[(a, b)] = -1

C = [-1] * N

def bfs(s):
    d = [-1] * N
    d[s] = 0
    p_old = [s]
    K = -1
    while p_old:
      p_new = []
      for i in p_old:
        c = 1
        for j in P[i]:
          if d[j] != -1:
            continue
          if C[i] == c:
            c += 1
          d[j] = 0
          p_new.append(j)
          C[j] = c
          AB[(i, j)] = c
          K = max(K, c)
          c += 1
      p_old = p_new
    return K

print((bfs(0)))

for x in list(AB.values()):
  print(x)


import sys
sys.setrecursionlimit(10**9)
n = int(input())
ab = []
t = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(lambda x:int(x)-1,input().split())
  t[a].append(b)
  t[b].append(a)
  ab.append((min(a,b),max(a,b)))
k = max(map(len,t))
d = {}
def dfs(pre,cur,col):
  cn = 1 if col != 1 else 2
  for i in t[cur]:
    if i == pre:
      continue
    d[(min(i,cur),max(i,cur))] = cn
    dfs(cur,i,cn)
    cn += 1
    if col == cn:
      cn += 1
dfs(0,0,0)
print(k)
for i in ab:
  print(d[i])

from collections import defaultdict, deque, Counter

N = int(input())

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

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

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

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

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

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


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a,b in ab:
	print((color[(a-1, b-1)]))


def main():
    import sys
    readline = sys.stdin.buffer.readline

    from collections import deque

    n = int(readline())
    ab = [list(map(int, readline().split())) for _ in range(n-1)]

    l = [[] for _ in range(n+1)]
    for a, b in ab:
        l[a].append(b)
        l[b].append(a)

    parents = [-1] * (n+1)
    order = []
    q = deque()
    q.append(1)
    while q:
        c = q.pop()
        order.append(c)
        for i in l[c]:
            if i == parents[c]:
                continue
            parents[i] = c
            q.append(i)
    
    color = [-1] * (n+1)
    for i in order:
        ng = color[i]
        c = 1
        for j in l[i]:
            if j == parents[i]:
                continue
            if c == ng:
                c += 1
            color[j] = c
            c += 1
    
    ans = []
    for a, b in ab:
        if a == parents[b]:
            ans.append(color[b])
        else:
            ans.append(color[a])

    print(max(ans))
    print('\n'.join(list(map(str, ans))))

def __starting_point():
    main()
__starting_point()

import sys
from collections import deque

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

n = int(input())
g = [[] for _ in range(n)]
e = []
for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    g[a - 1].append(b - 1)
    e.append(b - 1)

stack = deque([0])
stack.append(0)
ans = [0 for _ in range(n)]
while stack:
    v = stack.popleft()
    c = 1
    for nv in g[v]:
        if ans[v] == c:
            c += 1
        ans[nv] = c
        c += 1
        stack.append(nv)

print((max(ans)))
for i in e:
    print((ans[i]))


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


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, ABs):
    tree_top = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        tree_top[ABs[i][0]].append(i)
        tree_top[ABs[i][1]].append(i)

    max_color = 0
    for tt in tree_top:
        max_color = max(max_color, len(tt))

    ans = [0 for _ in range(N - 1)]
    for tt in tree_top:
        colored = []
        for i in tt:
            if ans[i] != 0:
                colored.append(ans[i])
        colored.sort()
        now_color = 1
        colored_point = 0
        for i in tt:
            if ans[i] != 0:
                continue
            if colored_point < len(colored) \
                    and now_color == colored[colored_point]:
                now_color += 1
                colored_point += 1
            ans[i] = now_color
            now_color += 1

    print(max_color)
    for a in ans:
        print(a)


def __starting_point():
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    # As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    ABs = [[int(i) for i in input().split()] for _ in range(N - 1)]
    solve(N, ABs)

__starting_point()

#BFSだとかえって考えにくい
#それぞれの頂点に対して塗られてない色で塗り分け
n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)
#print(paths)
for i in range(n):
    cand1,cand2=set(),[]
    #print(paths[i])
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])

import sys
sys.setrecursionlimit(10**6)
n=int(input())
g=[[] for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a-1]+=[(b-1,i)]
  g[b-1]+=[(a-1,i)]
l=[0]*(n-1)
def dfs(v,p=-1,s=-1):
  t=1
  for c,i in g[v]:
    if c==p: continue
    if t==s: t+=1
    l[i]=t
    dfs(c,v,t)
    t+=1
dfs(0)
print(max(l))
for i in l: print(i)

N = int(input())
G = [[] for n in range(N)]
vc = N*[0]
ec = (N-1)*[0]
h = 1

for n in range(N-1):
  a,b = map(int,input().split())
  G[a-1].append((b-1,n))

for v,g in enumerate(G):
  t = 1
  for b,i in g:
    if vc[v]==t:
      t+=1
    vc[b] = t
    ec[i] = t
    h = max(h,t)
    t+=1

print(h)
for n in range(N-1):
  print(ec[n])

from collections import deque
n=int(input())
g=[[] for _ in range(n+1)]
e=[]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    e.append(b-1)
 
q=deque([0])
 
color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1
 
        color[x]=c
        c+=1
        q.append(x)
 
print(max(color))
for i in e:
    print(color[i])

N = int(input())
l = [[] for i in range(N)]
li = []
for i in range(N-1):
  a, b = map(int, input().split())
  l[a-1].append(b-1)
  li.append([a-1, b-1])
  
ans = [-1] * N

for i in range(N):
  x = 0
  for j, h in enumerate(l[i]):
    if ans[i] == j:
      x += 1
    ans[h] = j+x
    
print(max(ans)+1)
for i in range(N-1):
  print(ans[li[i][1]]+1)

import sys
sys.setrecursionlimit(10000000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]

path = [list() for _ in range(N+1)]
for i in range(N-1):
    a, b = ab[i][0], ab[i][1]
    path[a].append([b, i])
    path[b].append([a, i])

color_max = 0
color_list = [0]*(N-1)
visit = [False]*(N+1)
visit[1] = True
def dfs(node, color, used_path):
    nonlocal visit
    nxt_color = 0
    for nxt in path[node]:
        nxt_node = nxt[0]
        use_path = nxt[1]
        if visit[nxt_node] == False:
            visit[nxt_node] = True
            nxt_color += 1
            if nxt_color == color:
                nxt_color += 1
            dfs(nxt_node, nxt_color, use_path)
    
    nonlocal color_list
    if used_path != -1:
        color_list[used_path] = color

dfs(1, 0, -1)


for c in color_list:
    color_max = max(c, color_max)
print(color_max)
print(("\n".join(map(str, color_list))))


from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=list(map(int,input().split()))
        edges.append((a,b))
        nList[a].append(b)
        #nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
        maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print((color[b]))

def __starting_point():
    n,nList,edges=readinput()
    main(n,nList,edges)

__starting_point()

import collections
N = int(input())
graph = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append([b-1,i])
    graph[b-1].append([a-1,i])

q = collections.deque()
ans = [-1]*(N-1)
q.append([0,-1])
while len(q) != 0:
    tmp = 1
    v, v2 = q.popleft()
    for w, i in graph[v]:
        if ans[i] != -1:
            continue
        if ans[v2] == tmp:
            tmp += 1
        ans[i] = tmp
        tmp += 1
        q.append([w,i])

print(len(set(ans)))
for i in ans:
    print(i)

#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(500000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def dfs(u, p, c, color, tree):
    color[(u, p)] = c
    color[(p, u)] = c

    now = 0
    for v in tree[u]:
        if v == p:
            continue
        if now == c:
            now += 1

        dfs(v, u, now, color, tree)
        now += 1


def solve():
    N = int(input())

    tree = [[] for _ in range(N)]
    edges = []
    for _ in range(N - 1):
        A, B = list(map(int, input().split()))
        A -= 1
        B -= 1
        tree[A].append(B)
        tree[B].append(A)
        edges.append((A, B))

    color = dict()
    dfs(0, -1, -1, color, tree)

    print((max(color.values()) + 1))
    for e in edges:
        print((color[e] + 1))


def main():
    solve()


def __starting_point():
    main()

__starting_point()

from sys import setrecursionlimit


setrecursionlimit(10**6)



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



hands = [0 for _ in range(n+1)]
for a, b in t:
    hands[a] += 1
    hands[b] += 1

number_of_colors = max(*hands)

def next_color(i):
    return i+1 if i < number_of_colors else 1



class edge():
    def __init__(self, en):
        self.ends = en
        self.color = 0

    def set_color(self, co):
        self.color = co

class nord():
    def __init__(self, tr):
        self.parent = tr
        self.edges = []

    def add(self, ed):
        self.edges.append(ed)

    def set_color(self, previous_color):
        co = next_color(previous_color)
        for ed in self.edges:
            if ed.color == 0:
                ed.set_color(co)
                for i in ed.ends:
                    no = self.parent.nords[i-1]
                    if self is not no:
                        no.set_color(co)
                co = next_color(co)

class tree():
    def __init__(self):
        self.nords = []

    def add_nord(self, no):
        self.nords.append(no)

    def add_edge(self, ed):
        for i in ed.ends:
            self.nords[i-1].add(ed)

    def set_color(self):
        self.nords[0].set_color(0)


tr = tree()
for _ in range(n):
    no = nord(tr)
    tr.add_nord(no)

e_tree = []
for en in t:
    ed = edge(en)
    e_tree.append(ed)
    tr.add_edge(ed)

tr.set_color()

print(number_of_colors)
for e in e_tree:
    print(e.color)

def main():
	N = int(input())
	vertex = [[] for i in range(N)]

	ini_v = 0
	for i in range(N - 1):
		a, b = [int(x) for x in input().split(" ")]
		if i == 0:
			ini_v = a - 1
		vertex[a - 1].append({"v": b - 1, "e": i})
		vertex[b - 1].append({"v": a - 1, "e": i})

	checked_v = [0] * N
	checked_e = [0] * (N - 1)
	to_visit = [ini_v]
	checked_v[ini_v] = 1
	color_e = [-1] * (N - 1)

	while len(to_visit):
		visiting = to_visit.pop(0)
		vs = vertex[visiting]
		used_cs = []
		cless_e = []
		for d in vs:
			if checked_v[d["v"]] == 0:
				checked_v[d["v"]] = 1
				to_visit.append(d["v"])
			if color_e[d["e"]] == -1:
				cless_e.append(d["e"])
			else:
				used_cs.append(color_e[d["e"]])
		s = 0
		for j in range(len(vs)):
			if s >= len(cless_e) or len(cless_e) == 0:
				break
			elif j in used_cs:
				continue
			else:
				color_e[cless_e[s]] = j
				s += 1

	print((max(color_e) + 1))
	for i in range(len(color_e)):
		print((color_e[i] + 1))

main()


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.popleft()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print(color[(a-1, b-1)])

import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n = ii()
    edge = [[] for _ in range(n)]
    ans = [0]*(n-1)
    for i in range(n-1):
        u, v = mi()
        u -= 1
        v -= 1
        edge[u].append((v, i))
        edge[v].append((u, i))
    k = 0
    q = deque([0])
    visited = [False]*n
    visited[0] = True
    c = [0]*n
    while q:
        v = q.popleft()
        cur = 1
        k = max(k, len(edge[v]))
        for nv, idx in edge[v]:
            if visited[nv]:
                continue
            if cur == c[v]:
                cur += 1
            visited[nv] = True
            c[nv] = cur
            ans[idx] = cur
            cur += 1
            q.append(nv)
    print(k)
    print(*ans, sep='\n')





def __starting_point():
    main()
__starting_point()

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *
 
N = INT()
ab = [LIST() for _ in range(N-1)]
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)

length = [len(x) for x in graph]
ans = max(length)

color = defaultdict(int)

q = deque([])
cnt = 1
for x in graph[0]:
	q.append((x, 0, cnt))
	cnt += 1

while q:
	n, previous, col = q.pop()
	cnt = 1
	for x in graph[n]:
		if x == previous:
			color[(n, x)] = col
			color[(x, n)] = col
		else:
			if cnt == col:
				cnt += 1
			color[(n, x)] = cnt
			color[(x, n)] = cnt
			q.append((x, n, cnt))
			cnt += 1

print(ans)
for a, b in ab:
	print((color[(a-1, b-1)]))


from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if len(G[a])<50:
      if prev[a] == 0:
        a_color=set([])
      else:
        a_color=set([G[a][prev[a]][1]])
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          for c in range(1,N+1):
            if c not in a_color:
              a_color.add(c)
              colors.append((G[a][b][0],c))
              G[a][b][1]=G[b][a][1]=c
              if c > cmax: cmax = c
              break
    else:
      temp = list(range(1,N))
      if prev[a] != 0:
        del temp[G[a][prev[a]][1]-1]
      temp = deque(temp)
      for i,b in enumerate(G[a]):
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          c = temp.popleft()
          colors.append((G[a][b][0],c))
          G[a][b][1]=G[b][a][1]=c
          if c > cmax: cmax = c
            
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix
# CreatedDate:  2020-09-15 21:36:31 +0900
# LastModified: 2020-09-15 22:19:28 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import deque


class BFS():
    def __init__(self, path, N):
        self.N = N
        self.color_path = [-1]*self.N
        self.path = path
        self.init = 1
        self.Q = deque([[0, self.init]])

    def forward(self):
        while self.Q:
            prev_path, u = self.Q.popleft()
            p_cnt = 1
            for cp, v in self.path[u]:
                if self.color_path[cp] == -1:
                    if prev_path == p_cnt:
                        p_cnt += 1
                    self.Q.append([p_cnt, v])
                    self.color_path[cp] = p_cnt
                    p_cnt += 1
#            print(self.color_path)

    def print_ans(self):
        self.color_path.pop(0)
        print((max(self.color_path)))
        for cp in self.color_path:
            print(cp)


def main():
    N = int(input())
    path = [[] for _ in range(N+1)]
    for i in range(1, N):
        a, b = list(map(int, input().split()))
        path[a].append([i, b])
        path[b].append([i, a])
    bfs = BFS(path, N)
    bfs.forward()
    bfs.print_ans()



def __starting_point():
    main()

__starting_point()

import sys 
from collections import deque,defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
graph = [[] for _ in range(N+1)]
AB = []
for i in range(N-1):
    a,b = map(int,readline().split())
    AB.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * (N+1)
dist[1] = 0
COL = defaultdict()
q = deque([(1,0)])
max_col = 0

def bfs(max_col):
    while q:
        x,pre_col = q.popleft()
        c = 1
        for nx in graph[x]:
            if dist[nx] != -1:
                continue
            if c == pre_col:
                c += 1
            COL[(x,nx)] = c
            dist[nx] = 1
            q.append((nx,c))
            max_col = max(max_col,c)
            c += 1
    return max_col  

max_col = bfs(max_col)
print(max_col)
for a,b in AB:
    if (a,b) in COL:
        print(COL[(a,b)])
    else:
        print(COL[(b,a)])

from collections import deque

N = int(input())
E = []
G = {i:set() for i in range(1, N+1)}
c = [-1 for i in range(N-1)]
for i in range(N-1):
  a, b = list(map(int, input().split()))
  E.append({a,b})
  G[a].add(i)
  G[b].add(i)
Q = deque([0])
c[0] = 1
while Q:
  i = Q.popleft()
  a, b = E[i]
  n = len(G[a])
  color = 0
  count = 0
  for ni in G[a]:
    if c[ni]==-1:
      c[ni] = color+1
      if c[ni] >= c[i]:
        c[ni] += 1
      color += 1
      Q.append(ni)
    else:
      count += 1
      if count > 1:
        break
  n = len(G[b])
  color = 0
  count = 0
  for ni in G[b]:
    if c[ni]==-1:
      c[ni] = color+1
      if c[ni] >= c[i]:
        c[ni] += 1
      color += 1
      Q.append(ni)
    else:
      count += 1
      if count > 1:
        break
print((max(c)))
for i in c:
  print(i)
      


import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return list(map(int,input().split()))
def lmp(): return list(map(int,input().split()))


n=int(input())
edge=[[] for i in range(n+1)]
par=[0]*(n+1)#i番目の頂点とその親を結ぶ辺の色
par[1]=-1
col=[0]*(n-1)#i番目の辺の色
for i in range(n-1):
    a,b=mp()
    edge[a].append([a,b,i])
    edge[b].append([b,a,i])


que=deque([edge[1]])
while len(que):
    k=1
    q=que.popleft()
    for x,y,i in q:
        if col[i]==0:
            if k==par[x]:
                k+=1
            col[i]=k
            par[y]=k
            k+=1
            que.append(edge[y])
print((max(col)))
for i in range(n-1):
    print((col[i]))

    


import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class Graph():
    def __init__(self, v):
        from heapq import heappop, heappush
        self.v = v
        self.graph = [[] for _ in range(v)]
        self.INF = 10 ** 9
    
    def addEdge(self, start, end, itr):
        self.graph[start].append((end, itr))
        self.graph[end].append((start, itr))
    
    def BFS(self, start):
        from collections import deque
        dist = [-1] * self.v
        ret = [0] * (self.v-1)
        que = deque()
        que.append((start, -1))
        dist[start] = 0
        while que:
            now, _color = que.popleft()
            color = 1
            if _color == color: color += 1
            for to, itr in self.graph[now]:
                if dist[to] == -1:
                    que.append((to, color))
                    dist[to] = dist[now] + 1
                    ret[itr] = color
                    color += 1
                    if color == _color: color += 1
        return ret
    
    def color_types(self):
        ret = len(self.graph[0])
        for x in self.graph[1:]:
            ret = max(ret, len(x))
        return ret

def Main():
    n = read_int()
    g = Graph(n)
    for i in range(n - 1):
        a, b = read_ints()
        g.addEdge(~-a, ~-b, i)
    print(g.color_types())
    print(*g.BFS(0), sep='\n')

def __starting_point():
    Main()
__starting_point()

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

n = int(input())
edge = [[] for _ in [0]*n]
for i in range(~-n):
    a, b = map(int, input().split())
    a -= 1;b -= 1
    edge[a] += [[b, i]]
ans = [0] * ~-n

def dfs(now, color):
    count = 1
    for to, i in edge[now]:
        # 親の色と同じとき
        if count == color:
            count += 1
        ans[i] = count
        dfs(to, count)
        count += 1

# 開始根は0番目に
dfs(0, 0)

print(max(ans))
for p in ans:
    print(p)

from collections import defaultdict
N = int(input())
edge = []
relation = defaultdict(set)
for i in range(N - 1):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    edge.append((a,b))
    relation[a].add(b)
    relation[b].add(a)

print(max(map(lambda x: len(relation[x]), relation)))
answer = {}
queue = []
queue.append((0, 0)) # (node_id, color_id)
already = set()
counter = 0
already.add(0)
while counter < len(queue):
    node, color = queue[counter]
    c = 1 if color != 1 else 2
    for n in relation[node]:
        if n not in already:
            queue.append((n, c))
            already.add(n)
            answer[(node, n)] = c
            c += 1
            if c == color:
                c += 1
    counter += 1
for e in edge:
    print(answer[e])

n = int(input())
a = [set() for i in range(n)]
e = []
for i in range(n-1):
  b, c = map(int, input().split())
  b -= 1
  c -= 1
  a[b].add(c)
  a[c].add(b)
  e.append(c)

col = [0 for i in range(n)]
visited = [False for i in range(n)]
visited[0] = True
v = [0]

while v:
  d = v.pop(0)
  k = 1
  for i in a[d]:
    if visited[i] == False:
      if col[d] == k:
        k += 1
      col[i] = k
      visited[i] = True
      v.append(i)
      k += 1

print (max(col))
for i in e:
  print (col[i])

import sys
sys.setrecursionlimit(10010010)

def abc146_d():
    n = int(input())
    Q = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(n-1)]

    deg = [0] * n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1: nouse = color[(min(s, p), max(s, p))]
        c = 1
        for t in adj[s]:
            if t == p: continue
            if c == nouse: c += 1
            color[(min(s, t), max(s, t))] = c
            dfs(t, s)
            c += 1

    dfs(1, -1)

    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

def __starting_point():
    abc146_d()
__starting_point()

from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
edge = []
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  edge.append((a,b))
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])
#print(tree)
ans = {}
while Q:
  temp = Q.popleft()
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now == col[temp]:
      now += 1
    col[n] = now
    ans[min(temp,n),max(temp,n)] = now
    now += 1
    Q.append(n)
    
print(m)
for a,b in edge:
  print(ans[(a,b)])

import sys
sys.setrecursionlimit(10**8)

def dfs(x, last=-1, ban_color=-1):
    """
    x: 今いる頂点
    last: 既に探索済の頂点(無限ループにならないように初期値-1)
    ban_color: 既に探索済の頂点(last)と今いる頂点(x)との辺に塗られている色(→使っちゃいけない色)
    """
    color = 1
    for to in vertex[x]:  #今いる頂点に隣接する頂点(つまり今いる頂点から出てる辺をすべて舐める),(rootから隣接する頂点に対してのroopとも捉えられる)
        if to == last: continue  # 既に探索済の辺はもう色が塗られているからスキップ
        if color == ban_color: color += 1
        color_dic[(x, to)] = color  # 辺の色をぬる
        dfs(to, x, color)
        color += 1
        
        

n = int(input())
vertex = {i: [] for i in range(n)} # 隣接頂点を保持
a = [0] * (n - 1)  #i番目の辺を保持
b = [0] * (n - 1)  #i番目の辺を保持
color_dic = {} # 辺の色を保持


for i in range(n-1): # 隣接頂点の辞書を作成
    a[i], b[i] = list(map(int, input().split()))
    a[i] -= 1
    b[i] -= 1
    vertex[a[i]].append(b[i])
    vertex[b[i]].append(a[i])

max_v = 0

for _, v in list(vertex.items()):
    if len(v) > max_v:
        max_v = len(v)
print(max_v)
    


dfs(0)

for i in range(n - 1):
    if (a[i], b[i]) in color_dic:
        print((color_dic[(a[i], b[i])]))
    else:
        print((color_dic[(b[i], a[i])]))
        



    


#!/usr/bin/env python3
import sys
sys.setrecursionlimit(200_000)

def solve(N: int, a: "List[int]", b: "List[int]"):
    from itertools import count
    edges = [[] for _ in range(N)]
    for i, (aa, bb) in enumerate(zip(a, b)):
        edges[aa-1].append((bb-1, i))
        edges[bb-1].append((aa-1, i))
    ans = [None] * (N-1)
    visited = set()
    def dfs(n, c):
        if n in visited:
            return
        visited.add(n)
        for (nn, i), cc in zip(filter(lambda x: x[0] not in visited, edges[n]),
                          filter(lambda y: y != c, count(1))):
            ans[i] = cc
            dfs(nn, cc)
    dfs(0, None)
    return [max(ans)] + ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
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
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(*solve(N, a, b), sep="\n")

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = [int(_) - 1 for _ in input().split()]
    edge[a].append((b, i))
    edge[b].append((a, i))
ans = [0] * (N - 1)
colors_num = max([len(_) for _ in edge])
colors = list(range(colors_num))


def dfs(v, pv, pc):
    valid_colors = [c for c in colors if c != pc]
    childs = list([c for c in edge[v] if c[0] != pv])
    for ((cv, ci), color) in zip(childs, valid_colors):
        ans[ci] = color + 1
        dfs(cv, v, color)


dfs(0, -1, -1)
print(colors_num)
print((*ans))


import sys
from collections import defaultdict, deque
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

g = [[] for _ in range(N)]
deg = [0] * N
ab = defaultdict(int)

for _ in range(N - 1):
    a, b = list(map(int1, readline().split()))
    g[a].append(b)
    g[b].append(a)
    deg[a] += 1
    deg[b] += 1
    ab[(a, b)] = -1

color = [-1] * N

print((max(deg)))

C = [0] * N
C[0] = -1

que = deque([0])

while len(que) != 0:
    idx = que.popleft()
    tmp = 1
    for i in g[idx]:
        if C[i] != 0:
            continue
        a, b = idx, i
        if tmp == C[idx]:
            tmp += 1
        ab[(a, b)] = tmp
        C[i] = tmp
        que.append(i)
        tmp += 1

for v in list(ab.values()):
    print(v)


import sys
readline = sys.stdin.readline

N = int(readline())

G = [[] for i in range(N)]
from collections import defaultdict
E = defaultdict(int)

for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  E[(a - 1, b - 1)] = i

from collections import deque
q = deque([])
ans = [None] * (N - 1)

q.append([0, -1, 0])
maxcol = 0
while q:
  v, parent, color = q.popleft()
  if color > maxcol:
    maxcol = color
  if (v, parent) in E:
    ans[E[(v, parent)]] = color
  elif (parent, v) in E:
    ans[E[(parent, v)]] = color
  next_col = 0
  for child in G[v]:
    if child == parent:
      continue
    next_col += 1
    if next_col == color:
      next_col += 1
    q.append([child, v, next_col])
    
print(maxcol)
for a in ans:
  print(a)

from collections import deque

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

l = [[] for _ in range(n+1)]
for a, b in ab:
    l[a].append(b)
    l[b].append(a)

parents = [-1] * (n+1)
order = []
q = deque()
q.append(1)
while q:
    c = q.pop()
    order.append(c)
    for i in l[c]:
        if i == parents[c]:
            continue
        parents[i] = c
        q.append(i)

color = [-1] * (n+1)
for i in order:
    ng = color[i]
    c = 1
    for j in l[i]:
        if j == parents[i]:
            continue
        if c == ng:
            c += 1
        color[j] = c
        c += 1

ans = []
for a, b in ab:
    if a == parents[b]:
        ans.append(color[b])
    else:
        ans.append(color[a])

print((max(ans)))
print(('\n'.join(list(map(str, ans)))))


#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque
def main():
    N = int(input())
    Node = [set() for _ in range(N)]
    Edge = {}
    for i in range(N-1):
        a , b = list(map(int, input().split()))
        a-=1
        b-=1
        if b<a:
            a, b = b, a
        Edge[(a, b)]=i
        Node[a].add(b)
        Node[b].add(a)

    K = 0
    for i, x in enumerate(Node):
        if len(x)>K:
            K = len(x)
            top = i


    q = deque()
    seen = [False]*(N-1)
    used = [set() for _ in range(N)]
    q.append(top)
    while len(q)>0:
        cur = q.popleft()
        col = 1
        for i in Node[cur]:
            if cur>i:
                ed = (i, cur)
            else:
                ed = (cur, i)
            if seen[Edge[ed]]==False:
                while col in used[cur] or col in used[i]:
                    col+=1
                seen[Edge[ed]] = col
                used[cur].add(col)
                used[i].add(col)
                q.append(i)

    print(K)
    print(('\n'.join(map(str, seen))))

def __starting_point():
    main()

__starting_point()

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for a, b in AB:
  graph[a].append(b)
  graph[b].append(a)
  
root = 1
parent = [0]*(N+1)
order = []
stack = [root]
while stack:
  x = stack.pop()
  order.append(x)
  for y in graph[x]:
    if y == parent[x]:
      continue
    parent[y] = x
    stack.append(y)
color = [-1]*(N+1)
for x in order:
  ng = color[x]
  c = 1
  for y in graph[x]:
    if y == parent[x]:
      continue
    if c == ng:
      c += 1
    color[y] = c
    c += 1
    
answer = []
for a, b in AB:
  if parent[a] == b:
    answer.append(color[a])
  else:
    answer.append(color[b])
K =max(answer)

print(K)
print('\n'.join(map(str, answer)))

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = LI_()
        G[a].append((b, i))
        G[b].append((a, i))

    ans = [0] * (N - 1)
    visited = [False] * N

    def dfs(c, color_p):
        visited[c] = True
        color = 0
        for n, i in G[c]:
            if not visited[n]:
                if color == color_p:
                    color += 1
                ans[i] = color
                dfs(n, color)
                color += 1

    dfs(0, -1)

    print((max(ans) + 1))
    for i in ans:
        print((i + 1))

def __starting_point():
    resolve()

__starting_point()

from collections import deque
def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    edges=[]
    for _ in range(n-1):
        a,b=list(map(int,input().split()))
        edges.append((a,b))
        nList[a].append(b)
        nList[b].append(a)
    return n,nList,edges

def bfs(s,nList):
    #print(nList)
    WHITE=0
    GRAY=1
    BLACK=2
    status=[WHITE]*(n+1)
    parent=[0]*(n+1)
    color=[0]*(n+1)
    maxcolor=0
    Q=deque([])
    Q.append(s)
    while(len(Q)>0):
        u=Q.popleft()
        usedcolor=color[u]
        col=1
        for t in nList[u]:
            if status[t]==WHITE:
                status[t]=GRAY
                parent[t]=u
                if col==usedcolor:
                    col+=1
                color[t]=col
                Q.append(t)
                col+=1
                maxcolor=max(maxcolor,col-1)
        status[u]=BLACK
        #print(u,usedcolor)
    return color, maxcolor


def main(n,nList,edges):
    color, maxcolor=bfs(1,nList)
    print(maxcolor)
    for a,b in edges:
        print((color[b]))

def __starting_point():
    n,nList,edges=readinput()
    main(n,nList,edges)

__starting_point()

N=int(input())
l=[[] for i in range(N)]
color=[0]*N
mem=[]
for i in range(N-1):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   mem.append(b)
from collections import deque
que=deque([0])
while que:
   node=que.popleft()
   c=1
   for i in l[node]:
      if color[node]==c:
         c+=1
      color[i]=c
      c+=1
      que.append(i)
print(max(color))
for i in mem:
   print(color[i])

from collections import deque

N = int(input())
# mtx = np.zeros([N, N], dtype=np.int32)
tree = [[] for i in range(N)]

key_order = [0] * (N-1)
for i in range(N-1):
    in1, in2 = map(int, input().split())
    in1 -= 1
    in2 -= 1
    tree[in1].append(in2)
    tree[in2].append(in1)

    key_order[i] = (in1, in2)

# [print(i, t) for i, t in enumerate(tree)]


def bfs(tree, p):
    seen = [False] * len(tree)
    queue = deque((p,))

    edge_colors = dict()
    node_colors = [0] * len(tree)
    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        parent_color = node_colors[q]

        cnt = 1
        for v in tree[q]:
            if not seen[v]:
                if cnt == parent_color:
                    cnt += 1

                edge_colors[(q, v)] = cnt
                node_colors[v] = cnt
                queue.append(v)
                cnt += 1



    """
    node_colors = [set() for _ in tree]
    edge_colors = dict()
    all_colors = set()
    color = 0

    while len(queue) > 0:
        q = queue.popleft()
        seen[q] = True

        for v in tree[q]:
            if not seen[v]:
                residual = all_colors - node_colors[q]
                if len(residual) > 0:
                    this_color = residual.pop()
                else:
                    color += 1
                    this_color = color
                edge_colors[(q, v)] = this_color
                node_colors[q].add(this_color)
                node_colors[v].add(this_color)
                all_colors.add(this_color)

                queue.append(v)
    """

    return edge_colors


edge_colors = bfs(tree, 0)

print(max([c for key, c in edge_colors.items()]))
[print(edge_colors[t]) for t in key_order]
# print(edge_colors)

# show_tree(tree)


from collections import deque

def main():
    n = int(input())
    adj = [[]for i in range(n+1)]
    ab = [list(map(int, input().split())) for i in range(n-1)]
    for a, b in ab:
        adj[a].append(b)
        adj[b].append(a)
    # dequeを使ったスタックによるDFS
    # 子をindexで、親ノードを要素で
    # 今回は彩色のためにどんな順番でpopされたかも保持しておく
    order  = []
    parent = [0] * (n+1)
    visited = [0] * (n+1)
    visited[1] = 1
    q = deque([1])
    while q:
        par = q.popleft()
        order.append(par)
        for chl in adj[par]:
            if visited[chl]:
                continue
            # 行ったことなかったら1へ
            visited[chl] = 1
            parent[chl] = par
            q.append(chl)
    # 彩色
    # 親と同じにならないように若い番号を割り当てて行く
    cl = [None] * (n+1)
    for par in order:
        # 親の色
        pc = cl[par]
        # 彩色は1以上k以下
        color = 1
        for chl in adj[par]:
            # 隣接リストの親は無視
            if chl == parent[par]:
                continue
            # 親の色と同じなら色を変える
            if pc == color:
                color += 1
            # カラーリストに子indexにcolorを入れる
            cl[chl] = color
            #　他の子は色を変える必要がある
            color += 1
    # 木グラフなので単純に次数最大で考えて問題ない
    g = max([len(i) for i in adj]) 
    print(g)   
    for a, b in ab:
        # 親子関係が逆転しない出力ならこれでいいがそうとも限らない 
        if parent[a] != b:
            print(cl[b])
        else:
            print(cl[a])
            
def __starting_point():
    main()
__starting_point()

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

graph = [[] for _ in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (n+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        
color = [-1] * (n+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue # 子に対応させる
        if c == ng:
            c += 1
        color[y] = c
        c += 1

print(max(color))
for a,b in ab:
    if parent[a] == b:
        print(color[a])
    else:
        print(color[b])

from collections import deque
N = int(input())
E = [[] for _ in range(N)]
  
for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  # 出力のために、何番目のEdgeだったかを保有させる必要がある
  E[a].append([i,b])
  E[b].append([i,a])
  
k = 0
for e in E:
  k = max(k, len(e))
print(k)


def bfs():
  colors = [-1 for _ in range(N-1)]
  visited = [False for _ in range(N)]
  d = deque()
  d.append([0,-1])
  while d:
    now,edge_color = d.pop()
    visited[now] = True
    cand_color = 1
    for i, nxt in E[now]:
      #print(i, nxt, visited[i], colors[i])
      if visited[nxt]:
        continue # TreeでBFSだとここは通らない・・・？
      if colors[i] > -1:
        assert("１エッジに２色塗ろうとする・・・？")
        continue
      if cand_color == edge_color:
        cand_color += 1
      colors[i] = cand_color
      d.append([nxt, colors[i]])
      cand_color += 1
  return colors

colors = bfs()

for i in range(len(colors)):
  print(colors[i])

import sys
from collections import deque

n = int(input())
G = [[] for _ in range(n + 1)]
G_order = []
# a<bが保証されている、aを親、bを子とする
for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    G[a].append(b)
    G_order.append(b)

# どこでも良いが、ここでは0をrootとする
que = deque([0])

# 各頂点と「親」を結ぶ辺の色
# 頂点0をrootとするのでC[0]=0で確定, 他を調べる
colors = [0] * n

while que:
    # prt = 親
    # 幅優先探索
    prt = que.popleft()
    color = 0

    # cld = 子
    for cld in G[prt]:
        color += 1
        # 「今考えている頂点とその親を結ぶ辺の色」と同じ色は使えない
        if color == colors[prt]:
            color += 1
        colors[cld] = color
        que.append(cld)

# それぞれの頂点とその親を結ぶ辺の色
# print(colors)

# 必要な最小の色数
print((max(colors)))

# 辺の番号順に色を出力
for i in G_order:
    print((colors[i]))


n=int(input())
l=[[] for _ in range(n)]
li=[]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  li.append([a-1,b-1])
ans=[-1]*n
for i in range(n):
  x=0
  for j,h in enumerate(l[i]):
    if ans[i]==j:
      x+=1
    ans[h]=j+x
print(max(ans)+1)
for i in range(n-1):
  print(ans[li[i][1]]+1)

from queue import Queue
N = int(input())
G = [[] for _ in range(N)]
Q = [{} for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    Q[a-1][b-1] = i

K = max(list(map(len, G)))
print(K)
ans = [0] * (N-1)
q = Queue()
q.put(0)
while not q.empty():
    v = q.get()
    c = set()
    for u in G[v]:
        if u < v:
            c.add(ans[Q[u][v]])
    
    i = 1
    for u in G[v]:
        if u > v:
            while i in c: i += 1
            ans[Q[v][u]] = i
            i += 1
            q.put(u)

for a in ans:
    print(a)

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())

def solve():
    n = INT()
    Q = [tuple(MAP1()) for _ in range(n-1)]

    deg = [0]*n
    adj = [[] for _ in range(n)]
    color = dict()

    for a, b in Q:
        deg[a] += 1
        deg[b] += 1
        adj[a].append(b)
        adj[b].append(a)

    def dfs(s, p):
        nouse = -1
        if p > -1:
            nouse = color[(min(s,p),max(s,p))]
        c = 1
        for t in adj[s]:
            if t == p:
                continue
            if c == nouse:
                c += 1
            color[(min(s,t),max(s,t))] = c
            dfs(t,s)
            c += 1
    
    dfs(1,-1)
    
    print(max(deg))
    for a, b in Q:
        print(color[(a, b)])

def __starting_point():
    solve()
__starting_point()

n = int(input())
A = []
g  =[[] for _ in range(n+1)]
ans = {}
for _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    A.append([a,b])
 
 
from collections import deque
 
q = deque()
q.append(1)
 
color = [-1]*(n+1)
color[1] = 0
cnt = 0
 
while q:
    v = q.popleft()
    p = 1
    for u in g[v]:
        if p==color[v]:
            p += 1
        color[u] = p
        ans[v,u] = p
        q.append(u)
        cnt = max(cnt,p)
        p += 1
print(cnt)
 
for i in range(n-1):
    tmp = (A[i][0],A[i][1])
    print(ans[tmp])

from collections import defaultdict, deque


N, *AB = map(int, open(0).read().split())
g = defaultdict(set)
edges = []
for a, b in zip(*[iter(AB)] * 2):
    a -= 1
    b -= 1
    g[a].add(b)
    g[b].add(a)
    edges.append((a, b))

q = deque([0])
visited = [False] * N
visited[0] = True
used = [0] * N
colors_cnt = 1
ans = {}
while q:
    v = q.popleft()
    color = 1
    for nv in g[v]:
        if visited[nv]:
            continue
        if color == used[v]:
            color += 1
        used[nv] = color
        ans[(min(v, nv), max(v, nv))] = color
        color += 1
        q.append(nv)
        visited[nv] = True
    colors_cnt = max(colors_cnt, color - 1)
print(colors_cnt)
[print(ans[(a, b)]) for a, b in edges]