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
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Colors_list = [[x for x in range(1, max_edges+1)] for x in range(n+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]

# print(Colors_list)

while dq:
    # Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    # for v in Visited_from:
    #     Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True

        use_color = Colors_list[node][0]
        Colors_list[node].remove(use_color)
        Colors_list[next_node].remove(use_color)

        Edge_colors[node][next_node] = use_color
        Edge_colors[next_node][node] = use_color

 #       del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

n = int(input())
Adj_dict = {x:[] for x in range(1,n+1)}
AB = []
for _ in range(n-1):
    a, b = map(int, input().split())
    Adj_dict[a].append(b)
    Adj_dict[b].append(a)
    AB.append([a,b])

max_edges = 0
node_max_edges = 0
for key, value in Adj_dict.items():
    edges = len(value)
    if edges >= max_edges:
        max_edges = edges
        node = key

dq = deque()
dq.append(node)

Visited = [False for _ in range(n+1)]
Visited[node] = True
Visited_to = [[] for _ in range(n+1)]

Colors = [x for x in range(1, max_edges+1)]
Edge_colors = [[-1 for _ in range(n+1)] for _ in range(n+1)]


while dq:
    Colors_copy = copy.deepcopy(Colors)    
    node = dq.popleft()
    Next_nodes = Adj_dict[node]

    Visited_from = Visited_to[node]
    for v in Visited_from:
        Colors_copy.remove(Edge_colors[node][v])

    for next_node in Next_nodes:
        if Visited[next_node] == True:
            continue
        dq.append(next_node)
        Visited_to[next_node].append(node)
        Visited[next_node] = True
        Edge_colors[node][next_node] = Colors_copy[0]
        Edge_colors[next_node][node] = Colors_copy[0]
        del Colors_copy[0]

print(max_edges)
for ab in AB:
    print(Edge_colors[ab[0]][ab[1]])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
edges = {}
lst = [set()for i in range(n)]
vert = [set() for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].add(b)
    lst[b-1].add(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    while lst[x-1]:
        i = lst[x-1].pop()
        lst[i-1].discard(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].add(j)
                vert[i-1].add(j)
                ans[edges[(a,b)]] = j
                break
print(max(ans))
for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
edges = {}
lst = [[]for i in range(n)]
vert = [set() for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].append(b)
    lst[b-1].append(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    for i in lst[x-1]:
        lst[x-1].remove(i)
        lst[i-1].remove(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].add(j)
                vert[i-1].add(j)
                ans[edges[(a,b)]] = j
                break
print(max(ans))
for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
edges = {}
lst = [[]for i in range(n)]
vert = [[]for i in range(n)]
ans = [0 for i in range(n-1)]
for i in range(n-1):
    a,b = map(int,input().split())
    lst[a-1].append(b)
    lst[b-1].append(a)
    if a > b:
        a,b = b,a
    edges[(a,b)] = i
q = deque([1])
while q:
    x = q.popleft()
    q.extend(lst[x-1])
    for i in lst[x-1]:
        lst[x-1].remove(i)
        lst[i-1].remove(x)
        a = min(x,i)
        b = max(x,i)
        for j in range(1,n):
            if not (j in vert[x-1] or j in vert[i-1]):
                vert[x-1].append(j)
                vert[i-1].append(j)
                ans[edges[(a,b)]] = j
                break
print(max(ans))
for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())

G = [[] for i in range(N+1)]
D = [0]*(N+1)
E = [[0]*(N+1) for i in range(N+1)]
Q = []
for i in range(N-1):
    a,b = map(int,input().split())
    Q.append((a,b))
    G[a].append(b)
    G[b].append(a)
    D[a]+=1
    D[b]+=1

mod = max(D)
print(mod)
def dfs(v,p):
    global G,D,E
    k = E[v][p]
    for c in G[v]:
        if c==p:continue
        k = (k+1)%mod
        E[v][c] = k
        E[c][v] = k
        dfs(c,v)
dfs(1,0)
for q in Q:print(E[q[0]][q[1]]+1)

Submission status: Time Limit Exceeded

Solution code:

import heapq
import collections
from collections import deque

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

colors = [ [-1] * (n + 1)  for _ in range(n + 1)] # abの色を格納
visit[1]=1

q = deque([(1,0)]) #V,color のtuple
K = 0
while q:
    v,from_color = q.popleft()
    c = 1
    for next_v in tree[v]:
        if visit[next_v] == -1:
            visit[next_v] = 1
            if c == from_color:
               c += 1
            colors[v][next_v] = colors[next_v][v] = c
            q.append((next_v,c))
            c += 1
anss = []
K = 0
for temp in ab:
    a,b = temp
    K = max(K, colors[a][b])
    anss.append(colors[a][b])

print(K)
for c in anss:
    print(c)





# for k,v in di:
#     color = max(colors,len(v))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


def color_rest(dic, Gv, K):
    rest = [True] * (K+1)
    for g in Gv:
        rest[dic[g[1]]-1] = False
    Rest = deque([])
    for i,r in enumerate(rest[:K]):
        if r:
            Rest.append(i+1)
    return Rest


def BFS(G, N, start, K):
    que = deque([start])
    dic = {}
    for i in range(N - 1):
        dic[i] = 0

    while que:
        v = que.popleft()
        Res = color_rest(dic, G[v], K)

        for w in G[v]:
            if dic[w[1]]:
                continue
            color = Res.popleft()
            dic[w[1]] = color
            que.append(w[0])
    return dic


N = int(input())
G = [[] for i in range(N)]
V = [0 for i in range(N)]

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

K = max(V)
start = V.index(K)
dic = BFS(G, N, start, K)

print(K)
for ans in dic.values():
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def color_rest(dic, Gv, K):
    rest = [True] * K
    for g in Gv:
        color = dic[g[1]]
        if color:
            rest[color-1] = False

    Rest = deque([])
    for i,r in enumerate(rest):
        if r:
            Rest.append(i+1)
    return Rest


def BFS(G, N, start, K):
    que = deque([start])
    dic = {}
    for i in range(N - 1):
        dic[i] = 0

    while que:
        v = que.popleft()
        Res = color_rest(dic, G[v], K)

        for w in G[v]:
            if dic[w[1]]:
                continue
            color = Res.popleft()
            dic[w[1]] = color
            que.append(w[0])
    return dic


N = int(input())
G = [[] for i in range(N)]
V = [0 for i in range(N)]

# 頂点リストを作る
for i in range(N-1):
    a, b = map(int, input().split())
    G[a - 1].append((b - 1, i))
    G[b - 1].append((a - 1, i))
    V[a - 1] += 1
    V[b - 1] += 1

K = max(V)
start = V.index(K)
dic = BFS(G, N, start, K)

print(K)
for ans in dic.values():
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n = int(input())
    ab = []
    colors = [[-1 for _ in range(n)] for _ in range(n)]
    visit = [-1 for _ in range(n)]
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a-1, b-1])
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    visit[0]=0
    q = deque([0])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 + (1+d==visit[s])
                visit[i] = d
                q.append(i)
    print(max(visit))
    for a, b in ab:
        print(visit[b])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    n = int(input())
    ab = []
    colors = [[-1 for _ in range(n)] for _ in range(n)]
    visit = [-1 for _ in range(n)]
    tree = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int,input().split())
        ab.append([a, b])
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    visit[0] = 0
    q = deque([0])
    while q:
        s = q.pop()
        d = 0
        for i in tree[s]:
            if visit[i]<0:
                d += 1 +((d+1)==visit[s])
                colors[s][i] = visit[i] = d
                q.append(i)
    print(max([len(i) for i in tree]))
    for a, b in ab:
        print(colors[a-1][b-1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
colors = [[-1 for _ in range(n)] for _ in range(n)]
visit = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]
for i in range(n-1):
    a, b = ab[i]
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
visit[0] = 0
q = deque([0])
while q:
    s = q.popleft()
    d = 0
    for i in tree[s]:
        if visit[i]<0:
            d += 1 +((d+1)==visit[s])
            colors[s][i] = visit[i] = d
            q.append(i)
print(max([len(i) for i in tree]))
result = []
for a, b in ab:
    print(colors[a-1][b-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def dfs(T,colors,visit,q):
    if len(q)==0:
        return colors
    s = q.popleft()
    d = 0
    for i in T[s]:
        if visit[i]<0:
            d += 1
            d += (d==visit[s])
            colors[s][i] = d
            visit[i] = d
            q.append(i)
    return dfs(T,colors,visit,q)

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

colors = [[-1 for _ in range(n)] for _ in range(n)]
visit = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]

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

visit[0] = 0
colors = dfs(tree,colors,visit,deque([0]))
result = []
for a, b in ab:
    result.append(colors[a-1][b-1])
print(max(result))
for i in range(n-1):
    print(result[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = deque()

def bfs():
    max_cnt = 0
    while q:
        u = q.popleft()
        cnt = 1
        visited[u] = True
        for v in edges[u]:
            if visited[v]:
                continue
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.append(v)
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.append(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        visited[u] = True
        for v in edges[u]:
            if visited[v]:
                continue
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        for v in edges[u]:
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
        max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
import queue


N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
visited = [False] * N
q = queue.Queue()

def bfs():
    max_cnt = 0
    while not q.empty():
        u = q.get()
        cnt = 1
        for v in edges[u]:
            if colors[u][v] != -1:
                continue

            while cnt in colors[u]:
                cnt += 1

            colors[u][v] = cnt
            colors[v][u] = cnt
            q.put(v)
            max_cnt = max(max_cnt, cnt)
    return max_cnt


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

q.put(0)
max_cnt = bfs()
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
edges = [[] for _ in range(N)]
colors = [[-1 for _ in range(N)] for _ in range(N)]
max_cnt = 1
visited = [False] * N


def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    cnt = 1
    for v in edges[u]:
        if colors[u][v] != -1:
            continue

        while cnt in colors[u]:
            cnt += 1

        colors[u][v] = cnt
        colors[v][u] = cnt

        dfs(v)

    global max_cnt
    max_cnt = max(max_cnt, cnt)


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

dfs(0)
print(max_cnt)
for a, b in AB:
    print(colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
from itertools import permutations, combinations, accumulate
from collections import deque
from heapq import heappush, heappop, heapify

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

def main():
    n = int(input())
    a= [0] * (n-1)
    b = [0] * (n-1)
    g = [[] for _ in range(n+1)]
    c = [[0]*(n+1) for _ in range(n+1)]
    cn = 0

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

    for i in range(1, n+1):
        cc = [_ for _ in range(1, n) if _ not in c[i]]
        heapify(cc)
        for j in g[i]:
            c[i][j] = c[j][i] = heappop(cc)
            cn = max(cn, c[i][j])

    print(cn)
    for p, q in zip(a, b):
        print(c[p][q])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
G=[[] for i in range(n)]
HEN=[]
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    d["{}_{}".format(a-1,b-1)]=-1
    HEN.append([a-1,b-1])

ans=0
for l in G:
    ans=max(ans,len(l))
print(ans)
for i in range(n):
    color=[_+1 for _ in range(ans)]
    for j in G[i]:
        
       
        if d["{}_{}".format(min([i,j]),max([i,j]))]!=-1:
            color.remove(d["{}_{}".format(min([i,j]),max([i,j]))]) 
       
    
    for j in G[i]:
        if d["{}_{}".format(min([i,j]),max([i,j]))] ==-1:
            d["{}_{}".format(min([i,j]),max([i,j]))]=min(color)
            del color[0]

for l in HEN:
    print(d["{}_{}".format(l[0],l[1])])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [{0} for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    seen = [False]*N
    used = {0}

    def dfs(v):
        K = 0
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                can = (G_c[u] | G_c[next_v])
                d = can ^ used
                if can ^ used:
                    c = d.pop()
                else:
                    c = K + 1
                    K += 1
                    used.add(c)
                # print(u, next_v, G_c[u] | G_c[next_v], c)
                seen[next_v] = True
                colors[u, next_v] = c
                colors[next_v, u] = c
                G_c[u].add(c)
                G_c[next_v].add(c)
                todo.append(next_v)
                break
            else:
                todo.pop()
        return K
    K = dfs(0)
    # print(G_c)
    print(K)
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [{0} for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    seen = [False]*N
    K = 0
    used = {0}

    def dfs(v):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                can = (G_c[u] | G_c[next_v])
                if can ^ used:
                    c = max(can ^ used)
                else:
                    c = max(can) + 1
                    used.add(c)
                # print(u, next_v, G_c[u] | G_c[next_v], c)
                seen[next_v] = True
                colors[u, next_v] = c
                colors[next_v, u] = c
                G_c[u].add(c)
                G_c[next_v].add(c)
                todo.append(next_v)
                break
            else:
                todo.pop()
    dfs(0)
    # print(G_c)
    print(max(len(c) - 1 for c in G_c))
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    G_c = [{0} for _ in range(N)]
    edges = []
    colors = {}
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edges.append((a-1, b-1))
        colors[(a-1, b-1)] = -1
        colors[(b-1, a-1)] = -1
    seen = [False]*N
    K = 0
    used = {0}

    def dfs(v):
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v]:
                    continue
                if (G_c[u] | G_c[next_v]) ^ used:
                    c = max((G_c[u] | G_c[next_v]) ^ used)
                else:
                    c = max(G_c[u] | G_c[next_v]) + 1
                    used.add(c)
                # print(u, next_v, G_c[u] | G_c[next_v], c)
                seen[next_v] = True
                colors[u, next_v] = c
                colors[next_v, u] = c
                G_c[u].add(c)
                G_c[next_v].add(c)
                todo.append(next_v)
                break
            else:
                todo.pop()
    dfs(0)
    # print(G_c)
    print(max(len(c) - 1 for c in G_c))
    for e in edges:
        print(colors[e])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

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

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''



N = int(input())
A = []
B = []
for i in range(N-1):
    x1,y1=[int(i) for i in input().split()]
    A.append(x1)
    B.append(y1)

used = [[False] * (N+1) for i in range(N+1)]

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

for i in range(N-1):

    for j in range(N-1):
        if used[A[i]][j]==False and used[B[i]][j]==False:
            ans[i] = j
            used[A[i]][j] = True
            used[B[i]][j] = True
            break

maxi = 0
for i in range(N):

    for j in range(maxi+1, N):
        if used[i][j] == True:
            maxi=j

print(maxi+1)
for a in ans:
    print(a+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
l = [0 for i in range(n)]
l2 = []
l3 = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l2.append([a,b])
    l3[a].append(b)
    l3[b].append(a)
    l[a-1] += 1
    l[b-1] += 1
a = max(l)
print(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([1,0])
rl[1] = 1
cl = [[0 for i in range(n+1)] for i in range(n+1)]
while len(d):
    now,c = d.popleft()
    rl[now] = 1
    if c == 0:
        count = 1
        for i in l3[now]:
            cl[now][i] = count
            d.append([i,count])
            count += 1
    else:
        count = 1
        for i in l3[now]:
            if rl[i] == 0:
                if c == count:
                    count += 1
                cl[now][i] = count
                d.append([i,count])
                count += 1
for i in range(n-1):
    print(cl[l2[i][0]][l2[i][1]])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ab = [[list(map(int, input().split())),i] for i in range(n-1)]
ab.sort(key = lambda x:x[0][0])	
c = [[] for _ in range(n)]
for i in ab:
  c[i[0][0]-1].append([i[0][1],i[1]])
  c[i[0][1]-1].append([i[0][0],i[1]])
k = 0
for i in c:
  k = max(k,len(i))
col = [[0]*k for i in range(n)]
ans = []
for d in ab:
  for i in range(k):
    if col[d[0][0]-1][i]==0 and col[d[0][1]-1][i]==0:
      col[d[0][0]-1][i] = d[0][1]
      col[d[0][1]-1][i] = d[0][0]
      ans.append([d[1],i+1])
      break
ans.sort(key=lambda x:x[0])
print(k)
for i in ans:
  print(i[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
con = [set() for _ in range(N+1)]
res = {}

for ab in AB:
    con[ab[0]].add(ab[1])
    con[ab[1]].add(ab[0])
    res[tuple(ab)] = 0

max_len = 0
for i, c in enumerate(con):
    if max_len <= len(c):
        max_len = len(c)
        max_ind = i

colors = [set() for i in range(N+1)]
all_colors = set([i for i in range(1, max_len+1)])
q = deque()
q.append(max_ind)
node_state = [0]*(N+1)

while q != deque():
    v = q.pop()
    node_state[v] = 1
    for next_v in con[v]:
        if node_state[next_v] == 0:
            q.appendleft(next_v)
        if v < next_v:
            va = v
            vb = next_v
        else:
            va = next_v
            vb = v
        if res[(va, vb)] == 0:
            color = list(all_colors.difference(colors[va].union(colors[vb])))[0]
            res[(va, vb)] = color
            colors[va].add(color)
            colors[vb].add(color)

print(max_len)
for i in range(N-1):
    print(res[tuple(AB[i])])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

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

k=[0]*N

from collections import deque

q=deque([0])
C=[[-1]*N for i in range(N)]
p=[-1]*N

kmx=0
while q:
    x=q.popleft()
    for i in G[x]:
        if C[x][i]!=-1:continue
        if p[x]==k[x]:
            k[x]+=1

        C[x][i] = k[x]
        C[i][x] = k[x]
        p[i] = k[x]
        k[x] += 1
        kmx=max(kmx,k[x])
        q.append(i)

print(kmx)
for i in range(N-1):
    print(C[a[i]][b[i]]+1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
G=[[] for i in range(N)]
a=[]
b=[]

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

L=[]
for i in G:
    L.append(len(i))

K=max(L)
print(K)

k=[0]*N

from collections import deque

q=deque([0])
C=[[-1]*N for i in range(N)]
p=[-1]*N

while q:
    x=q.popleft()
    for i in G[x]:
        if C[x][i]!=-1:continue
        if p[x]==k[x]:
            k[x]+=1

        C[x][i] = k[x]
        C[i][x] = k[x]
        p[i] = k[x]
        k[x] += 1


        q.append(i)

for i in range(N-1):
    print(C[a[i]][b[i]]+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []
color = [set() for _ in range(n)]
ans = dict()
for i in range(n-1):
    a,b = map(int,input().split())
    edge.append([a,b])
    tree[a-1].append(b)
    tree[b-1].append(a)

work_q = deque([])
visited = set()
work_q.append(1)
visited.add(1)
while work_q:
    here = work_q.popleft()
    for i in tree[here-1]:
        col = 1
        if i not in visited:
            work_q.append(i)
            visited.add(i)
            while col in color[here-1]:
                col += 1
            color[here-1].add(col)
            color[i-1].add(col)
            ans[(here-1,i-1)] = col
            col += 1

print(max(ans.values()))
for i in range(n-1):
    print(ans[edge[i][0]-1,edge[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n)]
edge = []
max_c = [0]*n
color = [set() for _ in range(n)]
ans = dict()
for i in range(n-1):
    a,b = map(int,input().split())
    edge.append([a,b])
    tree[a-1].append(b)
    tree[b-1].append(a)
    max_c[a-1] += 1
    max_c[b-1] += 1
print(max(max_c))

work_q = deque([])
visited = set()
work_q.append(1)
visited.add(1)
while work_q:
    here = work_q.popleft()
    for i in tree[here-1]:
        col = 1
        if i not in visited:
            work_q.append(i)
            visited.add(i)
            while col in color[here-1]:
                col += 1
            color[here-1].add(col)
            color[i-1].add(col)
            ans[(here-1,i-1)] = col
            col += 1

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