Problem:


Score : 400 points

Problem Statement

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 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
read = sys.stdin.read

N, *ab = map(int, read().split())
graph = [[] for _ in range(N + 1)]

for a, b in zip(*[iter(ab)] * 2):
    graph[a].append(b)

color = [0] * (N + 1)
queue = deque([1])
color_v = [[] for _ in range(N + 1)]

while queue:
    V = queue.popleft()
    number = 1
    for v in graph[V]:
        if number in color_v[V]:
            number += 1
        color[v] = number
        color_v[V].append(number)
        color_v[v].append(number)
        queue.append(v)
        number += 1

print(max(color))
for a, b in zip(*[iter(ab)] * 2):
    print(color[b])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
node_list=[tuple([int(thing) for thing in input().split(" ")]) for i in range(N-1)]
graph={i+1:[] for i in range(N)}
coloured=[0 for i in range(N+1)]
#↑0から始まってる（ただしkeyはそのまま使える）
count=[]
for i in range(len(node_list)):
    node=node_list[i]
    a=node[0]
    b=node[1]
    graph[a].append((b,i))
    graph[b].append((a,i))
ranking=sorted(range(1,N),key=lambda x:len(graph[x]),reverse=True)

c_num=len(graph[ranking[0]])

ret=["" for i in range(N-1)]
def what_colour(a_bit,b_bit):
    i=0
    while True:
        if (2**i&a_bit!=0) or (2**i&b_bit!=0):
            i=i+1
            continue
        else:return i


for i in ranking:
    for thing in graph[i]:
        j=thing[0]
        num=thing[1]

        c=what_colour(coloured[i],coloured[j])
        coloured[i]=coloured[i]+2**c
        coloured[j]=coloured[j]+2**c

        graph[j].remove((i,num))
        ret[num]=c
print(c_num)
for thing in ret:
    print(thing+1)

    #処理したらgraphから消してcolourdにビットで（2**色）を加算。処理する前にビット積（&が0になるか確かめる）

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CM = set(range(1,maxc+1))
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CC = CM.copy()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CC.remove(c)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])

Submission status: Time Limit Exceeded

Solution code:
def main():
  from sys import setrecursionlimit
  setrecursionlimit(100000)

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

  nodes = [[] for _ in range(N)]
  for a, b in ab:
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

  used = [set() for _ in range(N)]
  K = max(len(nodes[i]) for i in range(N))
  print(K)

  colors = [[-1] * N for _ in range(N)]

  def f(node, out, p, nodes, colors):
    cn = 1
    for n in nodes[node]:
      if n == p:
        continue
      if cn == out:
        cn += 1
      colors[node][n] = cn
      colors[n][node] = cn
      f(n, cn, node, nodes, colors)
      cn += 1

  f(0, -1, -1, nodes, colors)

  for a, b in ab:
    print(colors[a-1][b-1])
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  m = max(m,len(g[_]))
  mi = _
print(m)
g2 = [set(range(1,m+1)) for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      cu = (g2[cur]&g2[i]).pop()
      g2[cur].discard(cu)
      g2[i].discard(cu)
      d[(min(cur,i),max(cur,i))] = cu
for i in l:
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
E = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
K = 0
E_sorted = sorted(E, key=lambda x:x[0])
ans = {}
V = [[] for _ in range(N)]
for e in E_sorted:
  a, b = e
  c = 1
  req_K = True
  for i in range(1, K+1):
    if not (i in V[a]):
      c = i
      req_K = False
      break
  if req_K:
    K += 1
    c = K
  V[a].append(c)
  V[b].append(c)
  ans[e] = c
print(K)
for e in E:
  print(ans[e])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = set([i for i in range(1, 10**5)])
s = [[] for _ in range(N)]
r = []
for _ in range(N-1):
  a, b = map(int, input().split())
  n = min(A - set(s[a-1] + s[b-1]))
  s[a-1] += [n]
  s[b-1] += [n]
  r.append(n)

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

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
a = []
b = []
for i in range(N-1):
    a.append(ab[i][0])
for i in range(N-1):
    b.append(ab[i][1])
    
ab_max = []
for i in range(N-1):
    ab_max.append(a[i])
    ab_max.append(b[i])
c = collections.Counter(ab_max)    
    
ans = max(c.values())

print(ans)

l = [i for i in range(1, N+1)]

ndic = {}
for i in range(1, N+1):
    ndic[i] = []

for i in range(N-1):
    a_and_b = set(l) ^ (set(ndic[a[i]]).union(set(ndic[b[i]])))
    p = min(a_and_b)
    print(p)
    ndic[a[i]].append(p)
    ndic[b[i]].append(p)

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
cnt = 0
while Q and cnt < N-1:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
        cnt += 1
print(col)
for a, b in ed:
    print(colors[a*N + b])

Submission status: Time Limit Exceeded

Solution code:
import collections
from collections import defaultdict
N = int(input())
edges = []
vertexes = []
count = defaultdict(int)
parent = {}
childs = defaultdict(list)
color_dict = defaultdict(dict)
for i in range(N-1):
  a, b = map(int, input().split())
  parent[b] = a
  childs[a].append(b)
  edges.append((a,b))
  vertexes.append(a)
  vertexes.append(b)
  
#print(edges)
#print(vertexes)
#print(parent)
#childs = dict(childs)
#print(childs)

c = collections.Counter(vertexes)
max_color = max(c.values())
print(max_color)

parent_color = {1: -1}
for i in range(1, N):
  if i not in childs:
    continue
  pc = parent_color[i]
  allowed_colors = [j for j in range(1, max_color + 1) if j != pc]
  for child, color in zip(childs[i], allowed_colors):
    color_dict[i][child] = color
    parent_color[child] = color
    
#print(color_dict)

for e in edges:
  print(color_dict[e[0]][e[1]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a=[]
b=[]
for i in range(N-1):
    tmpa,tmpb=map(int,input().split())
    a.append(tmpa)
    b.append(tmpb)
c = a
c.extend(b)

max_num = 0
used = {}
for i in range(N):
    tmp = c.count(i+1)
    if tmp > max_num:
        max_num = tmp
    used[i] = []
print(max_num)

for i in range(N-1):
    for k in range(max_num):
        if not k in used[a[i]-1] and not k in used[b[i]-1]:
            print(k+1)
            used[a[i]-1].append(k)
            used[b[i]-1].append(k)
            break

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)

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

nodes = [[] for _ in range(N)]
for a, b in ab:
  nodes[a-1].append(b-1)
  nodes[b-1].append(a-1)

used = [set() for _ in range(N)]
K = max(len(nodes[i]) for i in range(N))
print(K)

colors = [[-1] * N for _ in range(N)]

def f(node, out, p):
  cn = 1
  for n in nodes[node]:
    if n == p:
      continue
    if cn == out:
      cn += 1
    colors[node][n] = cn
    colors[n][node] = cn
    f(n, cn, node)
    cn += 1

f(0, -1, -1)

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

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    colors[a*N + b] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
cnt = 0
while Q and cnt < N-1:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
        cnt += 1
print(col)
for a, b in ed:
    print(colors[a*N + b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
col = [[] for _ in range(N+1)]
Num = set([i for i in range(1,N+1)])

ans = []
AB = [list(map(int,input().split())) for _ in range(N-1)]
for ab in AB:
    left = ab[0]
    right = ab[1]
    i = min(list(Num - set(col[left]) -  set(col[right])))
    ans.append(i)
    col[left].append(i)
    col[right].append(i)

K = len(set(ans))
print(K)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [[0]*N for _ in range(N)]
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    cnt_edges[a-1]+=1
    cnt_edges[b-1]+=1
    A.append((a-1,b-1))
#%%
K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = [i for i in range(1,K+1)]
    if(used_color!=0):
        available_color.remove(used_color)
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        col = available_color.pop()
        next_stk.append((next,col))

        colors[next][n] = col
        colors[n][next] = col
    stk = next_stk + stk
    seen.add(n)

print(K)
for edge in A:
    a,b = edge
    col = colors[a][b]
    print(col)

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    n = int(raw_input())
    colors = {}
    all_edges = {}
    edges = {}
    order = []
 
    for i in xrange(1,n+1):
        edges[i] = []
        colors[i] = set()
        
    for i in xrange(n-1):
        a,b = map(int,raw_input().split())
        edges[a].append(b)
        edges[b].append(a)
        all_edges[(a,b)] = 0
        order.append((a,b))

    heap = []
    k = 0
    for i in edges.keys():
        heapq.heappush(heap,(-len(edges[i]),i))
        k = max(k,len(edges[i]))

    visited = set()
    while heap:
        i = heapq.heappop(heap)[1]
        #print(i)
        if i not in visited:
            visited.add(i)
            for kid in edges[i]:
                if kid not in visited:
                    for j in xrange(1,k+1):
                        if (j not in colors[i]) and (j not in colors[kid]):
                            colors[kid].add(j)
                            colors[i].add(j)
                            all_edges[(min(i,kid),max(i,kid))] = j
                            break
 
    print k
    for i in order:
        print all_edges[i]
 
main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
node_list=[tuple([int(thing) for thing in input().split(" ")]) for i in range(N-1)]
graph={i+1:[] for i in range(N)}
coloured=[0 for i in range(N+1)]
#↑0から始まってる（ただしkeyはそのまま使える）
count=[]
for node in node_list:
    a=node[0]
    b=node[1]
    graph[a].append(b)
    graph[b].append(a)
ranking=sorted(range(1,N),key=lambda x:len(graph[x]),reverse=True)

c_num=len(graph[ranking[0]])

ret=["" for i in range(N-1)]
def what_colour(a_bit,b_bit):
    i=0
    while True:
        if (2**i&a_bit!=0) or (2**i&b_bit!=0):
            i=i+1
            continue
        else:return i


for i in ranking:
    for j in graph[i]:
        c=what_colour(coloured[i],coloured[j])
        coloured[i]=coloured[i]+2**c
        coloured[j]=coloured[j]+2**c
        graph[j].remove(i)
        for k in range(N-1):
            ses=set(node_list[k])
            if i in ses and j in ses:
                ret[k]=c
print(c_num)
for thing in ret:
    print(thing+1)

    #処理したらgraphから消してcolourdにビットで（2**色）を加算。処理する前にビット積（&が0になるか確かめる）

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=[0]*(n-1)
    b=[0]*(n-1)
    for i in range(n-1):
        a[i],b[i] = map(int,input().split())
    import collections
    k=collections.Counter(a+b).most_common()[0][1]
    color_list=list(range(k))
    
    tree=[[] for _ in range(n)]
    for i in range(n-1):
        tree[a[i]-1].append(b[i])
        tree[b[i]-1].append(a[i])
        
    used_colors=[[] for _ in range(n)]
    ans=dict()
    q = [(1,0)]
    while q:
        x,parent = q.pop()
    #    if not x in checked:        checked.append(x)
        if parent!=0:
            for i in color_list:
                if not i in used_colors[parent-1]:
                    current_color=i
                    break
            used_colors[parent-1].append(current_color)
            used_colors[x-1].append(current_color)
        
            ans[str(parent)+"_"+str(x)]=current_color
        for y in tree[x-1]:
            if y == parent:
                continue
            q.append((y,x))
    
    print(k)
    for i in range(n-1):
        s=str(a[i])+"_"+str(b[i])
        print(ans[s]+1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
g = [[] for i in range(n)]
l = [0] * (n-1)
for _ in range(n-1):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  l[_] = (min(a,b),max(a,b))
  g[a].append(b)
  g[b].append(a)
m = 0
for _ in range(n):
  m = max(m,len(g[_]))
  mi = _
print(m)
g2 = [[0]*(m+1) for i in range(n)]
deq = deque([mi])
vi = [0] * n
vi[mi] = 1
d = dict()
while deq:
  cur = deq.popleft()
  for i in g[cur]:
    if vi[i] == 1:
      continue
    else:
      vi[i] = 1
      deq.append(i)
      for k in range(1,m+1):
        if g2[cur][k] == 1 or g2[i][k] == 1:
          continue
        else:
          g2[cur][k] = 1
          g2[i][k] = 1
          d[(min(cur,i),max(cur,i))] = k
          break
for i in l:
  print(d[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
K = 0
edges = [[0]*N for _ in range(N)]
cnt_edges = [0]*N
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1][b-1] = -1
    edges[b-1][a-1] = -1

    cnt_edges[a-1]+=1
    cnt_edges[b-1]+=1
    A.append((a-1,b-1))

K = max(cnt_edges)

stk = [(0,0)]
while(stk):
    n,used = stk.pop()
    available_color = [i for i in range(1, K+1)]
    if(used!=0):
        available_color.remove(used)
    for ind,i in enumerate(edges[n]):
        if(i==-1):
            col = available_color.pop()
            edges[n][ind] = col
            edges[ind][n] = col
            stk.append((ind, col))
print(K)
for a,b in A:
    print(edges[a][b])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CM = set(range(1,maxc+1))
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  #for v in V[u]:
  #  if CE[(min(u,v),max(u,v))] != 0:
  #    CU.add(CE[(min(u,v),max(u,v))])
  CC = CM-CU
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])

Submission status: Time Limit Exceeded

Solution code:
import collections
from collections import defaultdict
N = int(input())
edges = []
vertexes = []
count = defaultdict(int)
parent = {}
childs = defaultdict(list)
color_dict = defaultdict(dict)
for i in range(N-1):
  a, b = map(int, input().split())
  parent[b] = a
  childs[a].append(b)
  edges.append((a,b))
  vertexes.append(a)
  vertexes.append(b)
  
#print(edges)
#print(vertexes)
#print(parent)
#childs = dict(childs)
#print(childs)

c = collections.Counter(vertexes)
max_color = max(c.values())
print(max_color)

parent_color = {1: -1}
for i in range(1, N):
  if i not in childs:
    continue
  pc = parent_color[i]
  allowed_colors = [j for j in range(1, max_color + 1) if j != pc]
  for child, color in zip(sorted(childs[i]), allowed_colors):
    color_dict[i][child] = color
    parent_color[child] = color
    
#print(color_dict)

for e in edges:
  print(color_dict[e[0]][e[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])

last_color = 0
bfs_use_coler = [[] for _ in range(N+1)]

def solve(n,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    for val in tree[n]:
        if already_make[val[1]] != -1:
            continue
        use_coloer = -1
        length = last_color+1
        for i in range(1,length):
            if i in bfs_use_coler[val[0]] or i in bfs_use_coler[n]:
                continue
            else:
                use_coloer = i
                break
        if use_coloer == -1:
            last_color +=1
            use_coloer = last_color
        bfs_use_coler[val[0]].append(use_coloer)
        bfs_use_coler[n].append(use_coloer)
        already_make[val[1]] = use_coloer
    return last_color

for i in range(1,N+1):
    last_color = solve(i,last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    colors[a*N + b] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
while Q:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[a*N + b])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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

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

graph = defaultdict(list)

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

K = 0
for i in graph:
	K = max(K, len(graph[i]))
color = list(range(1, K+1))

def DFS(i, color_from):  # color_fromからきた色を使わない
	tmp = -1
	for node in graph[i]:	
		if not edge[i][node]:
			use_color = color[tmp]
			if use_color == color_from:
				use_color = color[tmp-1]
				tmp -= 1
			tmp -= 1
			edge[i][node] = use_color
			edge[node][i] = use_color
			DFS(node, use_color)

DFS(0, None)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
N = int(input())
tree = [[] for _ in range(N+1) ]
already_make = [-1]*(N+1)
for i in range(1,N):
    a,b = map(int,input().split(' '))
    tree[a].append([b,i])
    tree[b].append([a,i])

last_color = 0
bfs_use_coler = [[] for _ in range(N+1)]

def solve(n,last_color):
    '''
    use_colers =[]
    for val in bfs_use_coler[0:n-2]:
        use_colers = use_colers + val
    '''
    for val in tree[n]:
        if already_make[val[1]] != -1:
            continue
        use_coloer = -1
        length = last_color+1
        for i in range(1,length):
            if i in bfs_use_coler[val[0]] or i in bfs_use_coler[n]:
                continue
            else:
                use_coloer = i
                break
        if use_coloer == -1:
            last_color +=1
            use_coloer = last_color
        bfs_use_coler[val[0]].append(use_coloer)
        bfs_use_coler[n].append(use_coloer)
        already_make[val[1]] = use_coloer
    return last_color

for i in range(1,N+1):
    last_color = solve(i,last_color)
print(last_color)
for val in already_make[1:N]:
    print(val)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
D = [[0] * N for n in range(N)]
maxi = -1
AB = [0] * (N-1)
for n in range(N-1):
    a, b = tuple([int(x) for x in input().strip().split()])
    AB[n] = (a, b)
    D[a-1][b-1] = '#'
    D[b-1][a-1] = '#'

maxc = 0

for i, d in enumerate(D):
    c = d.count('#')
    if c > maxc:
        maxc = c
        maxi = i

q = deque([])
c = 1
for i in range(N):
    if D[maxi][i] == '#':
        D[maxi][i] = c
        D[i][maxi] = c
        c += 1
        q.append(i)

while q:
    ind = q.popleft()
    c = 1
    for i in range(N):
        while c in D[ind]:
            c += 1
        if D[ind][i] == '#':
            D[ind][i] = c
            D[i][ind] = c
            c += 1
            if i not in q:
                q.append(i)

print(maxc)
for a, b in AB:
    print(D[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

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

# print(graph)

stack = [(0, -1)]
visited = [-1]*n

k = 0
while stack:
    node, color = stack.pop()
    visited[node] = 1

    if k < len(graph[node]):
        k = len(graph[node])
    tmp = 1
    for i, (child, child_color) in enumerate(graph[node]):
        if visited[child] == 1:

            continue
        if child_color == -1:
            if tmp == color:
                tmp += 1
            graph[node][i] = (child, tmp)
            stack.append((child, tmp))
            tmp +=1

print(k)
for a, b in ab:
    print(list(filter(lambda x: x[0]==(b-1), graph[a-1]))[0][1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    E[v].sort()
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
c = 1
for v in range(1, N):
    available = {c: True for c in range(1, K+1)}
    for u in E[v]:
        if v > u:
            e_idx = edge_idx[(u, v)]
            available[edge_color[e_idx]] = False
            continue
        e_idx = edge_idx[(v, u)]
        while not available[c]: c = (c + 1) % K if c + 1 != K else K
        edge_color[e_idx] = c
        c = (c + 1) % K if c + 1 != K else K
for i in range(N-1):
    print(edge_color[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]
#print(E)
V = [set() for _ in range(N+1)]
for a,b in E:
  V[a].add(b)
  V[b].add(a)
#print(V)
maxc = 0
for v in V:
  maxc = max(maxc,len(v))
#print(maxc)
CM = set(range(1,maxc+1))
CE = {}
for e in E:
  CE[e] = 0
#print(CE)

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] != 0:
      CU.add(CE[(min(u,v),max(u,v))])
  CC = CM-CU
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

dfs(1,0,1)
print(maxc)
for e in E:
  print(CE[e])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy
input = sys.stdin.readline

N = int(input())
edge = []
color_dict = {}
repn = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b))
    color_dict[(a, b)] = None
    repn[a].append(b)
    repn[b].append(a)

K = 0
for i in range(N):
    K = max(K, len(repn[i]))
color_set = set([i for i in range(1, K + 1)])
print(K)

q = [(0, K + 1)]
while q:
    u, color = q.pop()
    c_set = deepcopy(color_set)
    c_set.discard(color)
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            c = c_set.pop()
            color_dict[(u, v)] = c
            color_dict[(v, u)] = c
            q.append((v, c))

for pair in edge:
    print(color_dict[pair])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)

n = int(input())
graph = {i : [] for i in range(n)}
ls = []
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls.append((a,b))
    graph[a].append(b)
    graph[b].append(a)
_max = 0
_max_node = None
for k, v in graph.items():
    if len(v) > _max:
        _max = len(v)
        _max_node = k
colors = [[0 for i in range(n)] for j in range(n)]
que = deque()
color_dict = {i : set(range(1,1+_max)) for i in range(n)}
cur = _max_node
already = set()
while True:
    cnt = 1
    already.add(cur)
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            if _next not in already:
                que.append(_next)
                already.add(_next)
            candidate = color_dict[_next].intersection(color_dict[cur])
            cnt = list(candidate)[0]
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].remove(cnt)
            color_dict[_next].remove(cnt)
    if len(que) == 0:
        break
    cur = que.popleft()
print(_max)
for a, b in ls:
    print(colors[a][b])

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    colors[(a, b)] = 0
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
while Q:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[(min(cur, nex), max(cur, nex))] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[(a, b)])

Submission status: Time Limit Exceeded

Solution code:
import collections
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
AB_C=[0 for i in range(N-1)]
D=collections.Counter([i[0] for i in AB]+[i[1] for i in AB]).most_common()
M=D[0][1]
print(M)




data=[set() for i in range(N+1)]
idxdata=set([i for i in range(N-1)])
d=0
while idxdata:
    #print(idxdata)
    count_c=1
    delidx=set()
    for i in idxdata:
        a,b=AB[i]
        if a==D[d][0] or b==D[d][0]:
            while not(count_c not in data[a] and count_c not in data[b]):
                count_c+=1
            AB_C[i]=count_c
            data[a].add(count_c)
            data[b].add(count_c)
            delidx.add(i)
    d+=1
    idxdata=idxdata-delidx


for i in AB_C:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tree = [[0]*n for i in range(n)]
input_list = [0]*n
   
for i in range(n-1):
    a, b = map(int, input().split())
    input_list[i] = [a, b]
    tree[a-1][b-1] = -1
    tree[b-1][a-1] = -1

ans = 0
for i in range(n):
    key = tree[i].count(-1)
    if key > ans:
        ans = key
print(ans)

keyofkey = [[int(i) for i in range(1, ans+1)] for i in range(n)]

for i in range(n-1):
    a, b = input_list[i][0], input_list[i][1]
    key_list = list(set(keyofkey[a-1]) & set(keyofkey[b-1]))
    p = key_list[0]
    keyofkey[a-1].remove(p)
    keyofkey[b-1].remove(p)
    print(p)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].append(b)
        E[b].append(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [""] * (N - 1)

    cand = {i for i in range(1, K + 1)}

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        c, v = Q.popleft()
        C = cand - {c}
        for u in E[v]:
            if visited[u]:
                continue
            visited[u] = True
            c = C.pop()
            Q.append((c, u))
            A[memo[(v, u)]] = str(c)

    print(K)
    print("\n".join(A))

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
use = [[True] * (n-1) for _ in range(n)]
brcol = []
colors = -1
for _ in range(n-1):
    a, b = map(int, input().split())
    for colo in range(0, n-1):
        if use[a-1][colo] and use[b-1][colo]:
            use[a-1][colo] = False
            use[b-1][colo] = False
            brcol.append(colo+1)
            if colors < colo:
                colors = colo
            break
print(colors+1)
for co in brcol:
    print(co)