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

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


used = [0]*N
used[0] = 1
parent = [0]*N
color = [ [0]*N for _ in range(N)]
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    c = 1
    r = q.popleft()
    for j in T[r]:
        if used[j] == 0:
            used[j] = 1
            if c == parent[r]:
                c += 1
            color[r][j] = c
            color[j][r] = c
            parent[j] = c
            c += 1
            q.append(j)
    total = max(total,c-1)


print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


used = [0]*N
color = [ [0]*N for _ in range(N)]
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    k = 0
    c = 1
    r = q.popleft()
    if used[r] == 0:
        used[r] = 1
        m = min(T[r])
        if r > m:
            k = color[r][m]
            T[r].remove(m)
        for j in T[r]:
            if c == k:
                c += 1
            color[r][j] = c
            color[j][r] = c
            c += 1
            q.append(j)
        total = max(total,c-1)


print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


color = [ [0]*N for _ in range(N)]
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    k = 0
    c = 1
    r = q.popleft()
    m = min(T[r])
    if r > m:
        k = color[r][m]
        T[r].remove(m)
    for j in T[r]:
        if c != k:
            color[r][j] = c
            color[j][r] = c
        else:
            c += 1
            color[r][j] = c
            color[j][r] = c
        c += 1
        q.append(j)
    total = max(total,c-1)

print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Time Limit Exceeded

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


color = [ [0]*N for _ in range(N)]
total = 0
q = [0]

while(len(q) > 0):
    k = 0
    c = 1
    r = q[0]
    q.remove(r)
    m = min(T[r])
    if r > m:
        k = color[r][m]
        T[r].remove(m)
    for j in T[r]:
        if c != k:
            color[r][j] = c
            color[j][r] = c
        else:
            c += 1
            color[r][j] = c
            color[j][r] = c
        c += 1
        q.append(j)
    total = max(total,c-1)

print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Time Limit Exceeded

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

color = [ [0]*N for _ in range(N)]
total = 0
for i in range(N):
    for j in T[i]:
        if color[j][i] == 0:
            k = []
            c = 0
            for s in T[i]:
                k.append(color[i][s])
            while(True):
                if c not in k:
                    break
                c += 1
            color[i][j] = c
            color[j][i] = c
            total = max(total,c)
print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

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

    k = 0
    for i in adj:
        k = max(k, len(i))
    print(k)


    c = [[0]*n for _ in range(n)]
    d = deque([[0, 0]])
    visited = [0]*n
    visited[0] = 1
    c_l = [i for i in range(1, k+1)]
    while d:
        node, color = d.popleft()
        if color == 0:
            color_list = c_l
        else:
            color_list = c_l[:color-1] + c_l[color:]
        cnt = 0
        for x in adj[node]:
            if visited[x]:
                continue
            visited[x] = 1
            c[node][x] = color_list[cnt]
            d.append([x, color_list[cnt]])
            cnt += 1

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

    # c = [[0]*n for _ in range(n)]
    # visited = [0]*n
    # def dfs(node):
    #     visited[node] = 1
    #     color = 1
    #     for nextnode in adj[node]:
    #         if visited[nextnode]:
    #             continue
    #         c[node][nextnode] = color
    #         dfs(nextnode)
    #         color += 1


    # c = [[] for _ in range(n)]
    # for a,b in ab:
    #     a -= 1
    #     b -= 1
    #     for i in range(1, k+1):
    #         if not i in c[a] and not i in c[b]:
    #             c[a].append(i)
    #             c[b].append(i)
    #             print(i)
    #             break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

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

    k = 0
    for i in adj:
        k = max(k, len(i))
    print(k)


    c = [[0]*n for _ in range(n)]
    d = deque([[0, 0]])
    visited = [0]*n
    visited[0] = 1
    c_l = [i for i in range(1, k+1)]
    while d:
        node, color = d.popleft()
        if color == 0:
            color_list = c_l
        else:
            color_list = c_l[:color-1] + c_l[color:]
        cnt = 0
        for x in adj[node]:
            if visited[x]:
                continue
            visited[x] = 1
            c[node][x] = color_list[cnt]
            d.append([x, color_list[cnt]])
            cnt += 1

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
edges = [[int(i) for i in input().split()] for _ in range(N-1)]
edge_col = [0]*(N-1)
cols = [set() for _ in range(N)]
gp = [[] for _ in range(N)]

for ind, (a, b) in enumerate(edges):
    gp[a-1].append((b-1, ind))
    gp[b-1].append((a-1, ind))

seen = set()
stk = [0]
max_col = 0
while stk:
    pt = stk.pop()
    if(pt in seen):
        continue
    seen.add(pt)
    for nxt, ind in gp[pt]:
        if(nxt in seen):
            continue
        col = 1
        while col in cols[pt]:
            col += 1
        max_col = max(col, max_col)
        edge_col[ind] = col
        cols[pt].add(col)
        cols[nxt].add(col)

        stk.append(nxt)

print(max_col)
for i in edge_col:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edges = [[int(i) for i in input().split()] for _ in range(N-1)]
edge_col = [0]*(N-1)
cols = [set() for _ in range(N)]
gp = [[] for _ in range(N)]

for ind, (a, b) in enumerate(edges):
    gp[a-1].append((b-1, ind))
    gp[b-1].append((a-1, ind))

def dfs():
    seen = set()
    stk = [0]
    while stk:
        pt = stk.pop()
        if(pt in seen):
            continue
        seen.add(pt)
        for nxt, ind in gp[pt]:
            if(nxt in seen):
                continue
            col = 1
            while col in cols[pt]:
                col += 1
            edge_col[ind] = col
            cols[pt].add(col)
            cols[nxt].add(col)

            stk.append(nxt)

dfs()
print(max(edge_col))
for i in edge_col:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
T = [[]for i in range(N)]
A = []
D = [[0]*N for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
    A.append((a,b))
K = 0
for t in T:
    K = max(K,len(t))
print(K)
Q = deque([(0,-1,0)])
while Q:
    q = Q.popleft()
    v,p,k = q[0],q[1],q[2]
    ck = 1
    for c in T[v]:
        if ck==k:ck+=1
        if c!=p:
            if len(T[c])!=1:
                Q.append((c,v,ck))
            D[c][v] = ck
            D[v][c] = ck
            ck+=1
for a in A:
    print(D[a[0]][a[1]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[]for i in range(N)]
A = []
D = [[0]*N for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
    A.append((a,b))
K = 0
for t in T:
    K = max(K,len(t))
print(K)
Q = [(0,-1,0)]
while Q:
    q = Q.pop(-1)
    v,p,k = q[0],q[1],q[2]
    ck = 1
    for c in T[v]:
        if ck==k:ck+=1
        if c!=p:
            if len(T[c])!=1:
                Q.append((c,v,ck))
            D[c][v] = ck
            D[v][c] = ck
            ck+=1
for a in A:
    print(D[a[0]][a[1]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = [[]for i in range(N)]
A = []
D = [[0]*N for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
    A.append((a,b))
K = 0
for t in T:
    K = max(K,len(t))
print(K)
Q = [(0,-1,0)]
while Q:
    q = Q.pop(-1)
    v,p,k = q[0],q[1],q[2]
    ck = 1
    for c in T[v]:
        if ck==k:ck+=1
        if c!=p:
            Q.append((c,v,ck))
            D[c][v] = ck
            D[v][c] = ck
            ck+=1
for a in A:
    print(D[a[0]][a[1]])

Submission status: Time Limit Exceeded

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

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            if c in color_used[j]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            # if c in color_used[j]:
            #     continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[j]:
                continue
            if c in color_used[i]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            if c in color_used[j]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
edges=[]
count=[0]*N

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

ans_1=max(count)
terminal=count.index(ans_1)

edges2=[]
colors=[-1]*(N-1)
c_list=[tuple(range(ans_1))]*N
for i in range(N-1):
    xx,yy=edges[i][1],edges[i][2]
    edges2.append(tuple([edges[i][0], min( (xx+N-terminal)%N,(yy+N-terminal)%N ) ,max( (xx+N-terminal)%N,(yy+N-terminal)%N )]))
edges2.sort(key=lambda x:x[1])

while True:
    if len(edges2)==0:
        break
    edge=edges2.pop(0)
    e1,e2=edge[1],edge[2]
    cc= list(set(c_list[e1])&set(c_list[e2]))[0]

    z1=list(c_list[e1])
    z1.remove(cc)
    c_list[e1]=tuple(z1)
    z2=list(c_list[e2])
    z2.remove(cc)
    c_list[e2]=tuple(z2)
    colors[edge[0]]=cc

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class Node:
    def __init__(self, n):
        self.n = n
        self.rem_next_nodes = set()


def find_min_color(used_colors, a, b):
    color = 1
    while True:
        if color not in used_colors[a] and color not in used_colors[b]:
            return color
        color += 1


def main():
    n = int(input())
    edges = [[] for _ in range(n)]
    edge_pairs = []
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        edges[a].append(b)
        edges[b].append(a)
        edge_pairs.append((a, b))

    edge_colors = {}
    used_colors = [set() for _ in range(n)]

    visited = [False] * n
    node_queue = deque([0])

    while node_queue:
        curr_node = node_queue.pop()

        visited[curr_node] = True

        for next_node in edges[curr_node]:
            if visited[next_node]:
                continue

            node_queue.appendleft(next_node)

            a = min(curr_node, next_node)
            b = max(curr_node, next_node)

            min_color = find_min_color(used_colors, a, b)

            edge_colors[(a, b)] = min_color

            used_colors[a].add(min_color)
            used_colors[b].add(min_color)

    print(max(edge_colors.values()))
    for edge_pair in edge_pairs:
        print(edge_colors[edge_pair])


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
g = [[] for x in range(n+1)]
s = []
for _ in range(n-1):
    a,b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)
    s.append([a,b])

from collections import deque
color = [[-1]*(n+1) for x in range(n+1)]
index = []
q = deque()
q.append([1,0])
ans = 0
while q:
    num = 0
    p = q.popleft()
    for i in g[p[0]]:
        if color[p[0]][i]==-1:
            num += 1
            if p[1]==num:
                num += 1
            color[p[0]][i] = num
            color[i][p[0]] = num
            q.append([i,num])
            ans = max(ans,num)

print(ans)
for a,b in s:
    print(color[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a].append(b)
    edges[b].append(a)

color_num = 0
for i in range(N):
    if len(edges[i]) > color_num:
        color_num = len(edges[i])


color_stack = deque([[]])
node_stack = deque([0])
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = edges[current]
    if (len(used_colors)) == 0:
        can_color = [i+1 for i in range(color_num)]
    else:
        can_color = [i+1 for i in range(color_num) if i != used_colors[0]-1]
    for node in nodes:
        if reached[node]:
            continue
        color = can_color.pop()
        node_stack.append(node)
        color_stack.append([color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a].append(b)
    edges[b].append(a)

color_num = 0
for i in range(N):
    if len(edges[i]) > color_num:
        color_num = len(edges[i])


color_stack = deque([[]])
node_stack = deque([0])
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = edges[current]
    can_color = [i+1 for i in range(color_num)]
    for color in used_colors:
        can_color.remove(color)
    for node in nodes:
        if reached[node]:
            continue
        color = can_color.pop()
        node_stack.append(node)
        color_stack.append([color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a].append(b)
    edges[b].append(a)

color_num = 0
for i in range(N):
    if len(edges[i]) > color_num:
        color_num = len(edges[i])


color_stack = [[]]
node_stack = [0]
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = edges[current]
    can_color = [i+1 for i in range(color_num)]
    for color in used_colors:
        can_color.remove(color)
    for node in nodes:
        if reached[node]:
            continue
        color = can_color.pop()
        node_stack.insert(0, node)
        color_stack.insert(0, [color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[False for i in range(N)] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a][b] = True
    edges[b][a] = True

color_num = 0
for i in range(N):
    if sum(edges[i]) > color_num:
        color_num = sum(edges[i])


color_stack = [[]]
node_stack = [0]
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = [i for i in range(len(edges[current])) if edges[current][i] and not reached[i]]
    can_color = [i+1 for i in range(color_num)]
    for color in used_colors:
        can_color.remove(color)
    for node in nodes:
        color = can_color.pop()
        node_stack.insert(0, node)
        color_stack.insert(0, [color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
line_list = []
#ans = []
ans = [0 for _ in range(num - 1)]

for i in range(num - 1):
    a, b = map(int, input().split())
    s = 1
    if i == 0:
        line_list.append([a, b])
        #ans.append(s)
        ans[i] = s
    else:
        while s <= len(line_list):
            if not a in line_list[s - 1] and not b in line_list[s - 1]:
                line_list[s - 1].append(a)
                line_list[s - 1].append(b)
                #ans.append(s)
                ans[i] = s
                break
            else:
                s += 1
        else:
            line_list.append([a, b])
            #ans.append(s)
            ans[i] = s


print(len(line_list))
for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
line_list = []
ans = []

for i in range(num - 1):
    a, b = map(int, input().split())
    if i == 0:
        line_list.append([a, b])
        ans.append('1')
    else:
        s = 1
        while s <= len(line_list):
            if not a in line_list[s - 1] and not b in line_list[s - 1]:
                line_list[s - 1].append(a)
                line_list[s - 1].append(b)
                ans.append(s)
                break
            else:
                s += 1
        else:
            line_list.append([a, b])
            ans.append(len(line_list))

print(len(line_list))
for item in ans:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [[] for _ in range(n+1)]
s = [0 for _ in range(n+1)]
ll = []
for _ in range(n-1):
  ai,bi = map(int,input().split())
  l[ai].append(bi)
  l[bi].append(ai)
  ll.append([ai,bi])
  s[ai] += 1
  s[bi] += 1
mx = 0
for i in range(1,n+1):
  if s[i] > mx:
    mx = s[i]
    mxi = i
print(mx)
ans = [[0 for _ in range(n+1)] for _ in range(n+1)]
def dfs(a,b,c):
  i = 1
  for h in l[a]:
    if h != b:
      if i == c:
        i += 1
      ans[a][h] = i
      ans[h][a] = i
      dfs(h,a,i)
      i += 1
  return
dfs(mxi,0,0)
for xx in ll:
  print(ans[xx[0]][xx[1]])

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e=-1):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e >0:
    col_lis.remove(edge_color[e])
  #color = 1
  for w,f in adj[v]:
    if visited[w]==False:
      #if c==color: color+=1
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
      #color+=1

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e=-1):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e >0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)

dfs(1)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

Submission status: Time Limit Exceeded

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

N = int(input())
adj = [[] for _ in range(N+1)]
for e in range(1,N):
  a,b = map(int, input().split())
  adj[a].append((b,e))
  adj[b].append((a,e))

#print(adj)

col_num = max([len(ad) for ad in adj])
edge_color = [0]*N
visited = [False]*(N+1)

def dfs(v,e):
  visited[v] = True
  #print(v,e,edge_color)
  col_lis = [i for i in range(1,col_num+1)]
  if e != 0:
    col_lis.remove(edge_color[e])
  for w,f in adj[v]:
    if visited[w]==False:
      #continue
    #if edge_color[e] == 0:
    #print(col_lis)
      edge_color[f] = col_lis.pop(0)
      dfs(w,f)
  return None
#print(col_num)
dfs(N-1,0)

print(col_num)
for i in range(1,N):
  print(edge_color[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=deque([[1,0]])
k=0

while len(q)>0:
    u,c=deque.popleft(q)

    clrs=list(range(1,c))+list(range(c+1,len(g[u])+1))
    cnt=0

    for v,i in g[u]:
        if clst[i]==c:
            continue
        clst[i]=clrs[cnt]
        deque.append(q,[v,clst[i]])
        cnt+=1


    if len(clrs)>0:
        k=max(k,clrs[-1])

print(k)

for i in range(n-1):
    print(clst[i])

Submission status: Time Limit Exceeded

Solution code:
import heapq

n=int(input())
g=[[] for i in range(n+1)]
clst=[-1]*(n-1)

for i in range(n-1):
    a,b=list(map(int,input().split()))

    g[a].append([b,i])
    g[b].append([a,i])


q=[(1,0)]
k=0

while len(q)>0:
    u,c=heapq.heappop(q)

    clrs=list(range(1,c))+list(range(c+1,len(g[u])+1))
    cnt=0

    for v,i in g[u]:
        if clst[i]==c:
            continue
        clst[i]=clrs[cnt]
        heapq.heappush(q,(v,clst[i]))
        cnt+=1


    if len(clrs)>0:
        k=max(k,clrs[-1])

print(k)

for i in range(n-1):
    print(clst[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
N=int(input())
G=defaultdict(list)
Edges=defaultdict(int)
edges=[]
for i in range(N-1):
  a,b=map(int,input().split())
  G[a].append(b)
  Edges[(a,b)]=0
  edges.append([a,b])
def dfs(G,s):
  stack=deque()
  seen=[]
  stack.append(s)
  seen.append(s)
  prev=defaultdict(int)
  prev[s]=s
  k=1
  while len(stack)!=0:
    u=stack.pop()
    if u!=s:
      k=max(k,len(G[u])+1)
    else:
      k=max(k,len(G[u]))
    lst=[i for i in range(1,k+1)]
    if u!=s:
      lst.remove(Edges[(prev[u],u)]) 
    else:
      pass
    for v in G[u]:
      if v not in seen:
        num=lst.pop(0)
        Edges[(u,v)]=num
        seen.append(v)
        stack.append(v)
        prev[v]=u
  return k

K=dfs(G,1)
print(K)
for e in edges:
  a,b=e[0],e[1]
  print(Edges[(a,b)])