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


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

breadth_first_search(1,tree)
for i in range(n-1):
    start = edge[i][0]
    goal = edge[i][1]
    print(ans[start-1,goal-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]*K for i in range(N)]

from collections import deque

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

while q:
    x=q.popleft()
    for i in G[x]:
        if C[x][i]!=-1:continue
        for j in range(K):
            if k[x][j]==0:
                C[x][i]=j
                C[i][x]=j
                k[x][j]=1
                k[i][j]=1
                break
        q.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)


n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

mmk = [[0 for i in range(n+1)] for i in range(n+1)]

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            mmk[currentNode+1][childNodeIndex+1] = kk
            dfs(childNodeIndex, arr, kk)




data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in arr:
    a0 = ar[0]
    a1 = ar[1]
    print(mmk[a0][a1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

mmk = [[0 for i in range(n+1)] for i in range(n+1)]

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [0 for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            mmk[currentNode+1][childNodeIndex+1] = kk
            dfs(childNodeIndex, arr, kk)




data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in arr:
    a0 = ar[0]
    a1 = ar[1]
    print(mmk[a0][a1])

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [set() for _ in range(N+1)]
d = [0]*(N+1)
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append([a,b])
    tree[a].add(b)
    tree[b].add(a)
    d[a] += 1
    d[b] += 1

root = d.index(max(d))
l = len(tree[root])
print(l)
q = queue.Queue()
for i in range(1, l+1):
    y = tree[root].pop()
    if root < y:
        color[edges.index([root, y])] = i
    else:
        color[edges.index([y, root])] = i
    tree[y].remove(root)
    q.put([y, root, i])

for _ in range(N-1):
    child, parent, e = q.get()
    l = len(tree[child])
    if l < e:
        colors = range(1, l+1)
    else:
        colors = [x for x in range(1, l+2) if x != e]
    for c in colors:
        y = tree[child].pop()
        if child < y:
            color[edges.index(sorted([child, y]))] = c
        else:
            color[edges.index(sorted([y, child]))] = c
        tree[y].remove(child)
        q.put([y, child, c])

for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [set() for _ in range(N+1)]
d = [0]*(N+1)
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append([a,b])
    tree[a].add(b)
    tree[b].add(a)
    d[a] += 1
    d[b] += 1

root = d.index(max(d))
l = len(tree[root])
print(l)
q = queue.Queue()
for i in range(l):
    y = tree[root].pop()
    if root < y:
        color[edges.index([root, y])] = i + 1
    else:
        color[edges.index([y, root])] = i + 1
    tree[y].remove(root)
    q.put([y, root, i+1])

while not q.empty():
    child, parent, e = q.get()
    l = len(tree[child])
    if l < e:
        colors = range(1, l+1)
    else:
        colors = [x for x in range(1, l+2) if x != e]
    for i in range(l):
        y = tree[child].pop()
        if child < y:
            color[edges.index(sorted([child, y]))] = colors[i]
        else:
            color[edges.index(sorted([y, child]))] = colors[i]
        tree[y].remove(child)
        q.put([y, child, colors[i]])

for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [set() for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append([a,b])
    tree[a].add(b)
    tree[b].add(a)

root = tree.index(max(tree, key = lambda x:len(x)))
l = len(tree[root])
print(l)
q = queue.Queue()
for i in range(l):
    y = tree[root].pop()
    color[edges.index(sorted([root, y]))] = i + 1
    tree[y].remove(root)
    q.put([y, root, i+1])

while not q.empty():
    child, parent, e = q.get()
    l = len(tree[child])
    if l < e:
        colors = range(1, l+1)
    else:
        colors = [x for x in range(1, l+2) if x != e]
    for i in range(l):
        y = tree[child].pop()
        color[edges.index(sorted([child, y]))] = colors[i]
        tree[y].remove(child)
        q.put([y, child, colors[i]])

for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [set() for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append(set([a,b]))
    tree[a].add(b)
    tree[b].add(a)

root = tree.index(max(tree, key = lambda x:len(x)))
l = len(tree[root])
print(l)
q = queue.deque()
for i in range(l):
    y = tree[root].pop()
    color[edges.index(set([root, y]))] = i + 1
    tree[y].remove(root)
    q.append([y, root, i+1])

while len(q) != 0:
    child, parent, e = q.popleft()
    l = len(tree[child])
    if l < e:
        colors = range(1, l+1)
    else:
        colors = [x for x in range(1, l+2) if x != e]
    for i in range(l):
        y = tree[child].pop()
        color[edges.index(set([child, y]))] = colors[i]
        tree[y].remove(child)
        q.append([y, child, colors[i]])

for c in color:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append(set([a,b]))
    tree[a].append(b)
    tree[b].append(a)

root = tree.index(max(tree, key = lambda x:len(x)))
print(len(tree[root]))
q = queue.deque()
for i in range(len(tree[root])):
    y = tree[root][i]
    color[edges.index(set([root, y]))] = i + 1
    tree[y].remove(root)
    q.append([y, root, i+1])

while len(q) != 0:
    child, parent, e = q.popleft()
    l = len(tree[child])
    if l < e:
        colors = range(1, l+1)
    else:
        colors = [x for x in range(1, l+2) if x != e]
    for i in range(l):
        y = tree[child][i]
        color[edges.index(set([child, y]))] = colors[i]
        tree[y].remove(child)
        q.append([y, child, colors[i]])

for c in color:
    print(c)

Submission status: Time Limit Exceeded

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

for a, b in AB:
  e[a].append(b)
  e[b].append(a)
  
color = {}
for a, b in AB:
  color[(a, b)] = -1
  color[(b, a)] = -1
cidx = max([len(i) for i in e])

for itr, i in enumerate(e):
  cls = set(range(1, cidx + 1))
  cls -= set([color[(itr, k)] for k in i])
  for j in i:
    if color[(itr,j)] == -1 or color[(j,itr)] == -1:
      cl = cls.pop()
      color[(itr, j)] = cl 
      color[(j, itr)] = cl
      
print(cidx)
for i in AB:
  print(color[i])

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    dist = [[] for i in range(N)]
    c = [[] for _ in range(N)]
    l = 0
    d = defaultdict(tuple)
    for i in range(N-1):
        a,b = map(int,input().split())
        dist[a-1].append(b-1)
        l = max(l,len(dist[a-1]))
        d[(a-1,b-1)] = i

    q = deque([0])
    ans = [0 for _ in range(N-1)]
    while q:
        now = q.popleft()
        col = 1
        for fol in dist[now]:
            for i in range(col,N+1):
                if i not in c[now]:
                    ans[d[(now,fol)]] = i
                    c[now].append(i)
                    c[fol].append(i)
                    col += 1
                    break
            q.append(fol)
            
    print(max(ans))
    for i in ans:
        print(i)
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [[] for _ in range(N)]
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		to[a].append(b)
		to[b].append(a)
		l = max(len(to[a]),len(to[b]))
		ch=np.array([False]*(N-1))
		ch[e_colors[a]]=True
		ch[e_colors[b]]=True
		for j in range(N-1):
			if(ch[j]==False):
				e_colors[a].append(j)
				e_colors[b].append(j)
				ans_colors.append(j)
				if(max_color < j+1):
					max_color = (j+1)
				break
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i]+1)

main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
def search_color(edge,next_edge,color_check):
    ind=color_check[edge].index(True)
    color_check[edge][ind]=False
    color_check[next_edge][ind]=False
    return ind+1
#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    side_num_arr=list(map(lambda x :len(x),node))
    l=max(side_num_arr)
    print(l)
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n-1)]
    last_ind=1
    while last_ind<n:
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for i in node[queue[now]]:
            edge=i[0]
            ind=i[1]
            if side_num_arr[edge]<=0:
                continue
            side_num_arr[edge]-=1
            side_num_arr[queue[now]]-=1
            queue[last_ind]=edge
            last_ind+=1
            color[ind]=search_color(queue[now],edge,color_check)
        now+=1
    return color


    

n=int(input())
side=[list(map(int,input().split())) for _ in range(n-1)]
node=[[] for _ in range(n)]
ans=[0 for _ in range(n-1)]
for i in range(n-1):
    u=side[i][0]-1
    v=side[i][1]-1
    node[u].append([v,i])
    node[v].append([u,i])
#print(node)
ans=bfs(0,n,node)
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
def search_color(edge,next_edge,color_check):
    ind=color_check[edge].index(True)
    color_check[edge][ind]=False
    color_check[next_edge][ind]=False
    return ind
#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    side_num_arr=list(map(lambda x :len(x),node))
    l=max(side_num_arr)
    print(l)
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n-1)]
    last_ind=1
    while last_ind<n:
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for i in node[queue[now]]:
            edge=i[0]
            ind=i[1]
            if side_num_arr[edge]<=0:
                continue
            side_num_arr[edge]-=1
            side_num_arr[queue[now]]-=1
            queue[last_ind]=edge
            last_ind+=1
            color[ind]=search_color(queue[now],edge,color_check)
        now+=1
    return color


    

n=int(input())
side=[list(map(int,input().split())) for _ in range(n-1)]
node=[[] for _ in range(n)]
ans=[0 for _ in range(n-1)]
for i in range(n-1):
    u=side[i][0]-1
    v=side[i][1]-1
    node[u].append([v,i])
    node[v].append([u,i])
#print(node)
ans=bfs(0,n,node)
for i in ans:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
def search_color(edge,next_edge,color_check):
    ind=color_check[edge].index(True)
    color_check[edge][ind]=False
    color_check[next_edge][ind]=False
    return ind
#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    side_num_arr=list(map(lambda x :len(x),node))
    l=max(side_num_arr)
    print(l)
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n-1)]
    last_ind=1
    while last_ind<n:
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for i in node[queue[now]]:
            edge=i[0]
            ind=i[1]
            if side_num_arr[edge]<=0:
                continue
            side_num_arr[edge]-=1
            side_num_arr[queue[now]]-=1
            queue[last_ind]=edge
            last_ind+=1
            color[ind]=search_color(queue[now],edge,color_check)
        now+=1
    return color


    

n=int(input())
side=[list(map(int,input().split())) for _ in range(n-1)]
node=[[] for _ in range(n)]
ans=[0 for _ in range(n-1)]
for i in range(n-1):
    u=side[i][0]-1
    v=side[i][1]-1
    node[u].append([v,i])
    node[v].append([u,i])
#print(node)
ans=bfs(0,n,node)
for i in ans:
    print(i+1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

N=int(input())

node=[[0] for i in range(N)]
#print(node)
q=[]
for i in range(N-1):
    a,b=map(int,input().split())
    q.append([a-1,b-1,i])

q.sort(key=lambda x:x[0])

ans=0
for index in range(len(q)):
    frm,to,num=q[index][0],q[index][1],q[index][2]
    for i in range(1,10**5+1):
        if (i in node[frm]) or (i in node[to]):
            pass
        else:
            node[frm].append(i)
            node[to].append(i)
            q[index].append(i)
            ans=max(ans,i)
            break
            
print(ans)
q.sort(key=lambda x:x[2])
for item in q:
    print(item[3])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
import sys
input=sys.stdin.readline

N=int(input())

node=[[0] for i in range(N)]
#print(node)
q=[]
for i in range(N-1):
    a,b=map(int,input().split())
    q.append([a-1,b-1,i])

q.sort(key=lambda x:x[0])

ans=0
for index in range(len(q)):
    frm,to,num=q[index][0],q[index][1],q[index][2]
    for i in range(1,10**6):
        if (i in node[frm]) or (i in node[to]):
            pass
        else:
            node[frm].append(i)
            node[to].append(i)
            q[index].append(i)
            ans=max(ans,i)
            break
            
print(ans)
q.sort(key=lambda x:x[2])
for item in q:
    print(item[3])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
colors = set()
N = 0

def assign(assignment, u, prev_color):
    rest_colors = colors - {prev_color}
    for v, color in zip(tree[u], rest_colors):
        assignment[u,v] = color
        assign(assignment, v, color)

def main():
    global tree, colors, N
    N = int(input())
    colors = set(range(1, N))
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
edges = []
colors = set()
N = 0

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def to_tree(edges_, n):
    tree_ = {i:[] for i in range(1,n+1)}
    for a, b in edges_:
        tree_[a].append(b)
    return tree_

def assign(assignment, u, prev_color):
    lest_colors = colors - {prev_color}
    for v, color in zip(tree[u], lest_colors):
        assignment[u,v] = color
        assign(assignment, v, color)

def main():
    global tree, edges, colors, N
    N = int(input())
    colors = set(range(1,N))
    edges = tuple(readlines(N-1))
    tree = to_tree(edges, N)
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
edges = []
colors = set()
N = 0

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def to_tree(edges_, n):
    tree_ = {i:[] for i in range(1,n+1)}
    for a, b in edges_:
        tree_[a].append(b)
        tree_[b].append(a)
    return tree_

def suc(u, parent):
    for v in [v for v in tree[u] if (u,v) in edges and (u,v) != (u, parent)]:
        yield u, v

def assign(assignment, u, parent):
    suc_edges = suc(u, parent)
    if not suc_edges:
        return

    lest_colors = colors - {assignment.get((parent, u))}
    for edge, color in zip(suc_edges, lest_colors):
        assignment[edge] = color
        v = edge[0] if edge[1] == u else edge[1]
        assign(assignment, v, u)

def main():
    global tree, edges, colors, N
    N = int(input())
    colors = set(range(1,N))
    edges = list(readlines(N-1))
    tree = to_tree(edges, N)
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
edges = []
colors = set()
N = 0

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def to_tree(edges_, n):
    tree_ = {i:[] for i in range(1,n+1)}
    for a, b in edges_:
        tree_[a].append(b)
        tree_[b].append(a)
    return tree_

def suc(u, parent):
    for v in tree[u]:
        if (u, v) != (u, parent):
            yield u, v

def assign(assignment, u, parent):
    suc_edges = suc(u, parent)
    if not suc_edges:
        return

    lest_colors = colors - {assignment.get((parent, u))}
    for edge, color in zip(suc_edges, lest_colors):
        assignment[edge] = color
        v = edge[0] if edge[1] == u else edge[1]
        assign(assignment, v, u)

def main():
    global tree, edges, colors, N
    N = int(input())
    colors = set(range(1,N))
    edges = list(readlines(N-1))
    tree = to_tree(edges, N)
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(500000)

N = 0
colors = []

def readlines(n):
    for _ in range(n):
        a, b = map(int, input().split())
        yield a, b

def used_colors(assignment, u, v):
    return {color for e, color in assignment.items() if e[0] in (u, v) or e[1] in (u, v)}

def assign(assignment, edges):
    if not edges:
        return assignment
    
    local_assignment = assignment.copy()
    colored = used_colors(local_assignment, *edges[0])
    local_assignment[edges[0]] = [color for color in colors if color not in colored][0]
    return assign(local_assignment, edges[1:] if len(edges) > 1 else [])

def main():
    global N, colors
    N = int(input())
    colors = list(range(1,N+1))
    edges = list(readlines(N-1))
    ans = assign({}, edges)
    print(max(ans.values()))
    for e in edges:
        print(ans[e])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

N = int(input())

edges = [set() for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a] |= {(b, i)}
    edges[b] |= {(a, i)}

cur_nodes = [0]
ans = ['0'] * (N - 1)
edge_colors = [set() for _ in range(N)]
colors = set()
q = queue.Queue()
q.put(0)
while not q.empty():
    # print('cur_nodes', cur_nodes)
    v = q.get()
    next_nodes = []
    es = edges[v]

    color_cands = colors - edge_colors[v]
    new_edge_colors = set()
    for e in es:
        ei = e[1]
        if ans[ei] != '0':
            continue
        else:
            cc = color_cands - edge_colors[e[0]]
            if len(cc) == 0:    # Add new color
                c = len(colors) + 1
                colors |= {c}
            else:
                c = tuple(cc)[0]
            ans[ei] = str(c)
            edge_colors[e[0]] |= {c}
            color_cands -= {c}
            new_edge_colors |= {c}
            # print(node, e[0], c)
        if e[0] != v:
            q.put(e[0])
    # print('next_nodes', next_nodes)
    edge_colors[v] -= new_edge_colors

    cur_nodes = next_nodes

print(len(colors))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

N = int(input())

edges = [set() for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a] |= {(b, i)}
    edges[b] |= {(a, i)}

cur_nodes = [0]
ans = ['0'] * (N - 1)
edge_colors = [set() for _ in range(N)]
colors = set()
q = queue.Queue()
q.put(0)
while not q.empty():
    # print('cur_nodes', cur_nodes)
    v = q.get()
    next_nodes = []
    es = edges[v]
    for e in es:
        ei = e[1]
        if ans[ei] != '0':
            continue
        else:
            cc = colors - edge_colors[v] - edge_colors[e[0]]
            if len(cc) == 0:    # Add new color
                c = len(colors) + 1
                colors |= {c}
            else:
                c = list(cc)[0]
            ans[ei] = str(c)
            edge_colors[e[0]] |= {c}
            edge_colors[v] |= {c}
            # print(node, e[0], c)
        if e[0] != v:
            q.put(e[0])
    # print('next_nodes', next_nodes)
    cur_nodes = next_nodes

print(len(colors))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

N = int(input())

edges = [set() for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a] |= {(b, i)}
    edges[b] |= {(a, i)}

cur_nodes = [0]
ans = ['0'] * (N - 1)
edge_colors = [set() for _ in range(N)]
colors = set()
q = queue.Queue()
q.put(0)
while not q.empty():
    v = q.get()
    next_nodes = []
    es = edges[v]
    for e in es:
        ei = e[1]
        if ans[ei] != '0':
            continue
        else:
            cc = colors - edge_colors[v] - edge_colors[e[0]]
            c = len(colors) + 1 if len(cc) == 0 else list(cc)[0]
            ans[ei] = str(c)
            edge_colors[e[0]] |= {c}
            edge_colors[v] |= {c}
            colors |= {c}
        if e[0] != v:
            q.put(e[0])
    cur_nodes = next_nodes

print(len(colors))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

edges = [set() for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a] |= {(b, i)}
    edges[b] |= {(a, i)}

cur_nodes = [0]
ans = ['0'] * (N - 1)
edge_colors = [set() for _ in range(N)]
colors = set()
visited = {0}
while len(cur_nodes) != 0:
    next_nodes = []
    # print('cur_nodes', cur_nodes)
    for node in cur_nodes:
        es = edges[node]
        for e in es:
            ei = e[1]
            if ans[ei] != '0':
                continue
            else:
                cc = colors - edge_colors[node] - edge_colors[e[0]]
                c = len(colors) + 1 if len(cc) == 0 else list(cc)[0]
                ans[ei] = str(c)
                edge_colors[e[0]] |= {c}
                edge_colors[node] |= {c}
                colors |= {c}
                # print(node, e[0], c)
            # if e[0] != node:
            if e[0] not in visited:
                next_nodes.append(e[0])
    # print('next_nodes', next_nodes)
    visited |= set(next_nodes)
    cur_nodes = next_nodes

print(len(colors))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

edges = [set() for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a] |= {(b, i)}
    edges[b] |= {(a, i)}

cur_nodes = [0]
ans = ['0'] * (N - 1)
edge_colors = [set() for _ in range(N)]
colors = set()
while len(cur_nodes) != 0:
    next_nodes = []
    # print('cur_nodes', cur_nodes)
    for node in cur_nodes:
        es = edges[node]
        for e in es:
            ei = e[1]
            if ans[ei] != '0':
                continue
            else:
                cc = colors - edge_colors[node] - edge_colors[e[0]]
                c = len(colors) + 1 if len(cc) == 0 else list(cc)[0]
                ans[ei] = str(c)
                edge_colors[e[0]] |= {c}
                edge_colors[node] |= {c}
                colors |= {c}
                # print(node, e[0], c)
            if e[0] != node:
                next_nodes.append(e[0])
    # print('next_nodes', next_nodes)
    cur_nodes = next_nodes

print(len(colors))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

edges = [set() for _ in range(N)]
for i, ab in enumerate(ab_n):
    a = ab[0] - 1
    b = ab[1] - 1
    edges_a = edges[a]
    edges_b = edges[b]
    edges_a |= {(b, i)}
    edges_b |= {(a, i)}

cur_nodes = [0]
ans = ['0'] * (N - 1)
edge_colors = [set() for _ in range(N)]
colors = set()
while len(cur_nodes) != 0:
    next_nodes = []
    # print('cur_nodes', cur_nodes)
    for node in cur_nodes:
        es = edges[node]
        for e in es:
            ei = e[1]
            if ans[ei] != '0':
                continue
            else:
                cc = colors - edge_colors[node] - edge_colors[e[0]]
                c = len(colors) + 1 if len(cc) == 0 else list(cc)[0]
                ans[ei] = str(c)
                edge_colors[e[0]] |= {c}
                edge_colors[node] |= {c}
                colors |= {c}
                # print(node, e[0], c)
            if e[0] != node:
                next_nodes.append(e[0])
    # print('next_nodes', next_nodes)
    cur_nodes = next_nodes

print(len(colors))
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    edge.append({a,b})
    graph[a].append(b)
    graph[b].append(a)
k = max(len(i) for i in graph)

que = deque()
seen = [False]*n
ans = [0]*(n-1)
que.append((0, -1))
while len(que)>0:
    node, p_color = que.popleft()
    seen[node] = True
    color = 1
    for i in graph[node]:
        if seen[i]:
            continue
        if color==p_color:
            color += 1
        ans[edge.index({node,i})] = color
        que.append((i, color))
        color += 1
print(k)
[print(i) for i in ans]