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
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
edges = dict()
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)
    edges[(a, b)] = i
    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, set()]]
while Q:
    cur, prev, NG = Q.pop()
    for nex in adj[cur]:
        if nex == prev:
            continue
        colors[(min(cur, nex), max(cur, nex))] = min(cand-NG)
        Q.append([nex, cur, {min(cand-NG)}])
        NG.add(min(cand-NG))
print(col)
for a, b in ed:
    print(colors[(a, b)])

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)
root = 1
queue = deque([root])
color_v = [[] for _ in range(N + 1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
degree = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
node_color = [0 for i in range(n)]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append([b,i])
    degree[a] += 1
    degree[b] += 1


maxcolor = max(degree)
search_list = [0]
node_color[0] = 0

while search_list:
    new_search_list = []
    for i in search_list:
        if node_color[i] == 0:
            color_list = [ k for k in range(1,maxcolor+1) ]
        else:
            color_list = [ k for k in range(1,maxcolor+1) if k != node_color[i] ]
        p = 0
        for j, v in enumerate(connect_list[i]):
            a, b = v
            new_search_list.append(a)
            node_color[a] = color_list[p]
            connect_list[i][j] = [b,color_list[p]]
            p += 1
    search_list = new_search_list

ans_list = []
for i in connect_list:
    for j in i:
        ans_list.append(j)

ans_list.sort()
print(maxcolor)
for i in ans_list:
    print(i[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
EhasV = [set() for x in range(N)]
EE = [0] * (N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    EE[i] = {a,b}
    EhasV[a].add(i)
    EhasV[b].add(i)

K = len(max(EhasV,key=len))
Vcolor = [set(range(1,K+1)) for x in range(N)]

Ecolor = [-1] * (N-1)

q = deque()
q.append(0)
i = 1
while i:
    v1 = q.pop()
    i -= 1
    for e in EhasV[v1]:
        if Ecolor[e] != -1:
            continue
        color = Vcolor[v1].pop()
        Ecolor[e] = color
        edgeside = EE[e]
        edgeside.discard(v1)
        v2 = edgeside.pop()
        Vcolor[v2].discard(color)
        q.append(v2)
        i += 1

print(K)
i = 0
while i < N - 1:
    print(Ecolor[i])
    i += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cmap = [[0 for _ in range(n)] for _ in range(n)]
for l in e:
    cmap[l[0]-1][l[1]-1] = cmap[l[1]-1][l[0]-1]=-1
    
d = deque()
d.append(1)
while(d):
    ed = d.popleft() -1
    clist = list()
    usedc = set()
    for i in range(n):
        if cmap[ed][i]:
            clist.append([i, cmap[ed][i]])
            usedc.add(cmap[ed][i])
    for color in clist:
        if color[1] == -1:
            d.append(color[0]+1)
            cn = 1
            while(1):
                if cn in usedc:
                    cn+=1
                else:
                    usedc.add(cn)
                    break

            cmap[ed][color[0]] = cmap[color[0]][ed] = cn

for i in range(n-1):
    c[i] = cmap[e[i][0]-1][e[i][1]-1]

print(max(c))
for num in c:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = [i, -1]

mx = 0
used = [set() for i in range(N)]
ans = [0] * (N-1)
cnt = 0
for u in range(N):
    mx = max(mx, len(nodes[u]))
    for v in nodes[u]:
        a, b = min(u, v), max(u, v)
        if edges[(a, b)][1] == -1:
            color = 1
            while color in used[a] or color in used[b]:
                color += 1
            edges[(a, b)][1] = color
            used[a].add(color)
            used[b].add(color)
            i = edges[(a, b)][0]
            ans[i] = str(color)
            cnt += 1
            if cnt == N-1:
                break
    else:
        continue
    break
print(mx)
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = input()
    tree = {}
    edge = []
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        if a not in tree:
            tree[a] = {}
        if b not in tree:
            tree[b] = {}
        tree[a][b] = None
        tree[b][a] = None
        edge.append([a, b])
    colors = max(len(b) for b in tree.itervalues())
    print colors
    stack = [1]
    while stack:
        node = stack.pop()
        nei = tree[node]
        unused = iter(set(range(1, colors + 1)) - {c for c in nei.itervalues() if c is not None})
        for nex in nei.keys():
            if nei[nex] is not None:
                continue
            tree[nex][node] = nei[nex] = next(unused)
            stack.append(nex)
    for a, b in edge:
        print tree[a][b]


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
c = [set([]) for _ in range(N + 1)]
g = [[0] * (N + 1) for _ in range(N + 1)]
paths = []
for _ in range(N-1):
    a, b = map(int, input().split())
    paths.append((a, b))

cmax = 1

for a, b in paths:
    cnt = 1
    while True:
        if cnt not in c[a] and cnt not in c[b]:
            c[a].add(cnt)
            c[b].add(cnt)
            g[a][b] = cnt
            cmax = max(cmax, cnt)
            break
        cnt += 1

print(cmax)
for a, b in paths:
    print(g[a][b])

Submission status: Time Limit Exceeded

Solution code:
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))

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

    #print(edges)
    visited = set()
    for i in xrange(1,n):
        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[(i,kid)] = j
                            break

    print k
    for i in order:
        print all_edges[i]

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

import itertools


UNDEF = 0


def mex(s):
    for i in itertools.count(1):
        if i not in s:
            return i


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF for _ in range(n - 1)]
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        while len(cur_cols) < num_adj:
            nc = mex(cur_cols)
            cur_cols.add(nc)
            new_cols.add(nc)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    colors = {}
    all_edges = {}
    edges = {}
    order = []

    for i in range(1,n+1):
        edges[i] = []
        colors[i] = set()
        
    for i in range(n-1):
        a,b = map(int,input().split())
        edges[a].append(b)
        edges[b].append(a)
        all_edges[(a,b)] = 0
        order.append((a,b))

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

    #print(edges)
    visited = set()
    for i in range(1,n):
        if i not in visited:
            visited.add(i)
            for kid in edges[i]:
                if kid not in visited:
                    for j in range(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[(i,kid)] = j
                            break

    print(k)
    for i in order:
        print(all_edges[i])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
EhasV = [set() for x in range(N)]
EE = [0] * (N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    EE[i] = {a,b}
    EhasV[a].add(i)
    EhasV[b].add(i)

K = len(max(EhasV,key=len))
Vcolor = [set(range(1,K+1)) for x in range(N)]

Ecolor = [-1] * (N-1)

q = deque()
q.append(0)
while q:
    v1 = q.pop()
    for e in EhasV[v1]:
        if Ecolor[e] != -1:
            continue
        color = Vcolor[v1].pop()
        Ecolor[e] = color
        edgeside = EE[e]
        edgeside.discard(v1)
        v2 = edgeside.pop()
        Vcolor[v2].discard(color)
        q.append(v2)

print(*([K]+Ecolor),sep='\n')

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:
N = int(input())
c = [[] for _ in range(N + 1)]
g = [[0] * (N + 1) for _ in range(N + 1)]
paths = []
for _ in range(N-1):
    a, b = map(int, input().split())
    paths.append((a, b))

for a, b in paths:
    cnt = 1
    while True:
        if cnt not in c[a] and cnt not in c[b]:
            c[a].append(cnt)
            c[b].append(cnt)
            g[a][b] = cnt
            break
        cnt += 1

print(max([max(x) for x in g]))
for a, b in paths:
    print(g[a][b])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import itertools


UNDEF = 0


def mex(s):
    for i in itertools.count(1):
        if i not in s:
            return i


def color_edges(n, edges):
    adj_list = [set() for _ in range(n)]
    for i, (a, b) in enumerate(edges):
        adj_list[a].add(i)
        adj_list[b].add(i)
    colors = [UNDEF for _ in range(n - 1)]
    for v in range(n):
        adj_es = adj_list[v]
        num_adj = len(adj_es)
        cur_cols = set(colors[i] for i in adj_es if colors[i] != UNDEF)
        new_cols = set()
        while len(cur_cols) < num_adj:
            nc = mex(cur_cols)
            cur_cols.add(nc)
            new_cols.add(nc)
        for u in adj_es:
            if colors[u] == UNDEF:
                colors[u] = new_cols.pop()
    return max(colors), colors


def main():
    n = int(input())
    edges = []
    for _ in range(n - 1):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    k, cs = color_edges(n, edges)
    print(k)
    print(*cs, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N=int(input())
deg=[0 for v in range(N+1)];deg[0]=None
out=[set() for v in range(N+1)];deg[0]=None
for e in range(1,N):
    a,b=map(int,input().split())
    out[a].add((b,e));out[b].add((a,e))
for v in range(N+1):
    deg[v]=len(out[v])
# print(out) #DB
# print(deg) #DB

K=max(deg[1:])
# print(K) #DB

vcol=[set() for v in range(N+1)];vcol[0]=None # 頂点vから出る辺に含まれる色
ecol=[0 for e in range(N)];ecol[0]=None # 辺eの色
#r=[False for v in range(N+1)];r[0]=None # その頂点にたどり着いたか→vcolで代用

q=deque()
q.append(1)
while q:
    u=q.popleft() # 今いる頂点
    for vs in out[u]: # 今いる頂点の隣にある頂点と，その頂点に行くための辺の番号
        if not vcol[vs[0]]: # その頂点にまだ辿り着いていなければ（書き換え後）
        #if not r[vs[0]]: # その頂点にまだ辿り着いていなければ
            for col in range(1,K+1): # 各色を順に選び
                if col not in vcol[u]: # その色が，今いる頂点から生える辺にまだ使われていなければ
                    ecol[vs[1]]=col # その辺をその色で塗り
                    vcol[u].add(col) # 今いる頂点から生える辺の色の集合に加え
                    vcol[vs[0]].add(col) # 進んだ先の頂点から生える辺の色の集合に加える。
                    break
            # r[vs[0]]=True # その頂点にたどり着いたこととし（削る）
            q.append(vs[0]) # その頂点をキューに加える。

# print(vcol) #DB
# print(ecol) #DB

print(K)
for ecoli in ecol[1:]:
    print(ecoli)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

cmap = [[0 for _ in range(n)] for _ in range(n)]
for l in e:
    cmap[l[0]-1][l[1]-1] = cmap[l[1]-1][l[0]-1]=-1
    
d = deque()
d.append(1)
while(d):
    ed = d.pop() -1
    clist = list()
    usedc = set()
    for i in range(n):
        if cmap[ed][i]:
            clist.append([i, cmap[ed][i]])
            usedc.add(cmap[ed][i])
    for color in clist:
        if color[1] == -1:
            d.append(color[0]+1)
            cn = 1
            while(1):
                if cn in usedc:
                    cn+=1
                else:
                    usedc.add(cn)
                    break

            cmap[ed][color[0]] = cmap[color[0]][ed] = cn

for i in range(n-1):
    c[i] = cmap[e[i][0]-1][e[i][1]-1]

print(max(c))
for num in c:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
edges = {}
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
    edges[(a, b)] = [i, -1]

mx = 0
used = [set() for i in range(N)]
ans = [0] * (N-1)
for u in range(N):
    mx = max(mx, len(nodes[u]))
    for v in nodes[u]:
        a, b = min(u, v), max(u, v)
        if edges[(a, b)][1] == -1:
            color = 1
            while color in used[a] or color in used[b]:
                color += 1
            edges[(a, b)][1] = color
            used[a].add(color)
            used[b].add(color)
            i = edges[(a, b)][0]
            ans[i] = str(color)
print(mx)
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append(i)
    l[b-1].append(i)
from collections import deque
q=deque([1])
e[0]=1
m=10**6
while q:
    pc=q.popleft()
    p,c=pc//m,pc%m
    for vn in AB[p]:
        x=1
        for en in l[vn-1]:
            if e[en]==0:
                if x==c:
                    x=c+1
                q.append(en*m+x)
                e[en]=x
                x+=1
print(*([max(e)]+e),sep='\n')

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からきた色を使わない
	can_use_color = color.copy()
	for node in graph[i]:
		if not edge[i][node]:
			use_color = can_use_color.pop()
			if use_color == color_from:
				use_color = can_use_color.pop()
			edge[i][node] = use_color
			edge[node][i] = use_color
			DFS(node, use_color)

DFS(0, None)

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

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 : [] for i in range(n)}
cur = _max_node
while True:
    cnt = 1
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            que.append(_next)
            candidate = color_dict[_next] + color_dict[cur]
            while cnt in candidate:
                cnt = cnt + 1 if cnt + 1 <= _max else 1
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].append(cnt)
            color_dict[_next].append(cnt)
            cnt += 1
    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:
from collections import deque

N=int(input())
deg=[0 for v in range(N+1)];deg[0]=None
out=[set() for v in range(N+1)];deg[0]=None
for e in range(1,N):
    a,b=map(int,input().split())
    out[a].add((b,e));out[b].add((a,e))
for v in range(N+1):
    deg[v]=len(out[v])

# print(out) #DB
# print(deg) #DB

K=max(deg[1:])

# print(K) #DB


vcol=[set() for v in range(N+1)];vcol[0]=None # 頂点vから出る辺に含まれる色
ecol=[0 for e in range(N)];ecol[0]=None # 辺eの色
r=[False for v in range(N+1)];r[0]=None # その頂点にたどり着いたか

q=deque()
q.append(1);r[1]=True
while q:
    u=q.popleft() # 今いる頂点
    for vs in out[u]: # 今いる頂点の隣にある頂点と，その頂点に行くための辺の番号
        if not r[vs[0]]: # その頂点にまだ辿り着いていなければ
            for col in range(1,K+1): # 各色を順に選び
                if col not in vcol[u]: # その色が，今いる頂点から生える辺にまだ使われていなければ
                    ecol[vs[1]]=col # その辺をその色で塗り
                    vcol[u].add(col) # 今いる頂点から生える辺の色の集合に加え
                    vcol[vs[0]].add(col) # 進んだ先の頂点から生える辺の色の集合に加える。
                    break
            r[vs[0]]=True # その頂点にたどり着いたこととし
            q.append(vs[0]) # その頂点をキューに加える。

# print(vcol) #DB
# print(ecol) #DB

print(K)
for ecoli in ecol[1:]:
    print(ecoli)

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 : [] for i in range(n)}
cur = _max_node
while True:
    cnt = 1
    for _next in graph[cur]:
        if colors[cur][_next] == 0:
            que.append(_next)
            candidate = color_dict[_next] + color_dict[cur]
            while cnt in candidate:
                cnt = cnt + 1 if cnt + 1 <= _max else 1
            colors[cur][_next] = cnt
            colors[_next][cur] = cnt
            color_dict[cur].append(cnt)
            color_dict[_next].append(cnt)
            cnt += 1
    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, 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]))

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

DFS(0, None)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a,b = [],[]
for _ in range(N-1):
	at,bt = map(int,input().split())
	a.append(at)
	b.append(bt)

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

for i in range(N-1):
	E[a[i]].append(b[i])
	E[b[i]].append(a[i])

q = [[1,-1,0]]

ans = [[0 for _ in range(N+1)] for _ in range(N+1)]
cnt = 0
while q:
	cp, root, r_col = q.pop(0)
	
	i = 1
	for np in E[cp]:
		if np == root:
			continue
		if i == r_col:
			i += 1
		q.append([np,cp,i])
		ans[cp][np] = i
		ans[np][cp] = i
		cnt = max(cnt, i)
		i += 1

print(cnt)
for i in range(N-1):
	print(ans[a[i]][b[i]])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
l=[[] for i in range(N)]
e=[0]*(N-1)
for i,(a,b) in enumerate(AB):
    l[a-1].append(i)
    l[b-1].append(i)
from collections import deque
q=deque([(0,1)])
e[0]=1
while q:
    p,c=q.popleft()
    for vn in AB[p]:
        x=1
        for en in l[vn-1]:
            if e[en]==0:
                if x==c:
                    x=c+1
                q.append((en,x))
                e[en]=x
                x+=1
print(*([max(e)]+e),sep='\n')

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]))

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

while q:
	i, color_from = q.popleft()
	can_use_color = list(range(1, K+1))
	if color_from:
		can_use_color.remove(color_from)
	for node in graph[i]:
		if not edge[i][node]:
			use_color = can_use_color.pop()
			edge[i][node] = use_color
			edge[node][i] = use_color
			q.append((node, use_color))

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

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

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

e = [[] for _ in range(n)]
d = [[0 for _ in range(n)] for _ in range(n)]

c = [0] * n

for a, b in ab:
    c[a] += 1
    c[b] += 1
    e[a].append(b)
    e[b].append(a)

me = max(c)

print(me)

def func(x, p, pc):
    color = 1
    for z in e[x]:
        if color == pc:
            color += 1
        if z == p:
            continue
        else:
            d[x][z] = color
            d[z][x] = color
            func(z, x, color)
        color += 1

func(0, -1, -1)

for a, b in ab:
    print(d[a][b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph = [[] for i in range(N+1)] #graph[0]は使わない
edges = [list(map(int, input().split())) for _ in range(N-1)]

for i in range(N-1):
    a, b = edges[i]
    graph[a].append(b)
    graph[b].append(a)

colors = 1
for g in graph:
    colors = max(colors, len(g))
#colorsの数は決定
print(colors)

used = [set() for i in range(N+1)]
cur = 1

for a, b in edges:
    while cur in used[a] or cur in used[b]:
        cur += 1
        if cur > colors:
            cur = 1
    print(cur)
    used[a].add(cur)
    used[b].add(cur)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
node = [[]for i in range(N)]
side = []
ans = [0]*(N-1)
watch = [0]*N
watch[0] = 1
for i in range(N-1):
    a,b = map(int,input().split())
    side.append([a-1,b-1])
    node[a-1].append(i)
    node[b-1].append(i)

K = max(len(i) for i in node)
print(K)

queue = deque([0])

while queue:
    q = queue.popleft()
    use = [0]*(K+1)
    for i in node[q]:
        use[ans[i]] = 1
    p = 1
    for i in node[q]:
        if ans[i] == 0:
            while use[p]:
                p += 1
            ans[i] = p
            use[p] = 1
            s = side[i]
            next = s[(s.index(q)+1)%2]
            if watch[next] == 0:
                queue.append(next)
                watch[next] = 1

for i in ans:
    print(i)

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]))

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

DFS(0, None)

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