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:
N = int(input())
col = [[] for _ in range(N+1)]
Num = [i for i in range(1,N+1)]
ans = []
AB = [list(map(int,input().split())) for _ in range(N-1)]
for ab in AB:
    left = ab[0]
    right = ab[1]
    i = min(list(set(Num) - set(col[left]) & set(Num) - set(col[right])))
    ans.append(i)
    col[left].append(i)
    col[right].append(i)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def solve():
    N =  int(input())
    E = [[] for _ in range(N+1)]
    D = {}
    L = [-1 for _ in range(N)]
    for i in range(1,N):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
        D[(a,b)] = D[(b,a)] = i
    r = 1
    l = len(E[1])
    for i in range(2,N+1):
        k = len(E[i])
        if l < k:
            r, l = i, k
    d = l
    q = [(r,0)]
    z = []
    while q:
        v, c = q.pop()
        C = list(range(1,d+1))
        for u in E[v]:
            if L[D[(v,u)]] == -1:
                x = C.pop()
                if c == x:
                    x = C.pop()
                q.append((u,x))
                L[D[(v,u)]] = x
                z.append(u)
    L[0] = d
    res = '\n'.join(map(str, L))
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def p(tt, parent):
    children = tt[parent]
    res = {parent: children}
    for c, ii in children:
        res.update(p(tt, c))
    return res


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tt = defaultdict(list)

    for i, (a, b) in enumerate(ab):
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa

    tree = p(tt, 0)
    # print(tree)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tt[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

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

    A = [0] * (N - 1)

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

    visited = [False] * (N + 1)

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

    print(K)
    for a in A:
        print(a)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#abc146_d
import sys
import math
import collections
#sys.setrecursionlimit(100000)

n=int(input())

ai=[]
bi=[]
count = [0 for i in range(n+1)]

#print(count)
for i in range(n-1):
	tmp = input().split()
	a,b = list(map(lambda a: int(a), tmp))
	ai.append(a)
	bi.append(b)
	count[a]+=1
	count[b]+=1
#print(count)

maxapexcount=count[1]
maxapexno=1
for i in range(n+1):
	if(count[i]>maxapexcount):
		maxapexcount=count[i]
		maxapexno=i
print(maxapexcount)





listtmp = [[0 for i in range(n+1)] for j in range(n+1)]
#print(listtmp)
for i in range(n-1):
	#tmpstr=str(ai[i])+" "+str(bi[i])
	#print(tmpstr)
	for j in range(1,n):
		if(listtmp[ai[i]][j]!=1)and(listtmp[bi[i]][j]!=1):
			listtmp[ai[i]][j]=1
			listtmp[bi[i]][j]=1
			print(j)
			break

Submission status: Time Limit Exceeded

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

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

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

graph = defaultdict(list)

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

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

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

DFS(0, None)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
AB = [(a, b) for a, b in [map(int, line.split()) for line in sys.stdin]]
I = {AB[i]:i for i in range(len(AB))}
E1 = [set() for i in range(N)]
E2 = [[] for i in range(N)]
for a, b in AB:
  E1[a - 1].add(b - 1)
  E1[b - 1].add(a - 1)
  E2[a - 1].append(b - 1)
K = max([len(e) for e in E1])
print(K)
C1 = [{c for c in range(K)} for i in range(N)]
C2 = [0 for i in range(len(AB))]
for a in range(N):
  for b in E2[a]:
    c = C1[a].pop()
    C2[I[(a + 1, b + 1)]] = c
    C1[b].remove(c)
for c in C2:
  print(c + 1)

Submission status: Time Limit Exceeded

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

N = int(input())

A = [0]*N
L = [[0 for i in range(N)]for i in range(N)]
tmp = 0
tmp_a = 0
for i in range(N-1):
    a, b = map(int, input().split())
    if tmp_a != a:
        tmp_a = a
        tmp = 1
        
    for j in range(tmp, N+1):
        if L[a-1][j-1] == 0 and L[b-1][j-1] == 0:
            L[a-1][j-1]=1
            L[b-1][j-1]=1
            A[i] = j
            tmp = j
            break


print(max(A))
for i in range(N-1):
    print(A[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def p(tt, parent):
    children = tt[parent]
    for i in range(len(children)):
        if children[i][0] == parent:
            children.remove(children[i])
            break

    res = {parent: children}
    for c, ii in children:
        tt[c].remove((parent, ii))
        res.update(p(tt, c))
    return res


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tt = defaultdict(list)

    for i, (a, b) in enumerate(ab):
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa
        a, b = b, a
        aa = tt[a]
        aa.append((b, i))
        tt[a] = aa

    tree = p(tt, 0)
    # print(tree)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tt[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

def func(s):
    return int(s)-1


N=int(input())
e=[list(map(func,input().split()))+[i] for i in range(N-1)]
e.sort()

x=[0 for i in range(N)]
for i in range(N-1):
    x[e[i][0]]+=1
    x[e[i][1]]+=1
print(max(x))

e2=[[0 for j in range(x[i])]for i in range(N)]
ans=[0 for i in range(N-1)]

for i in range(N-1):
    [p,q,r]=e[i]
    for j in range(x[p]):
        if e2[p][j]==0:
            e2[p][j]=1
            if j<x[q]: e2[q][j]=1
            ans[r]=j
            break
        
for i in range(N-1):
    print(ans[i]+1)

Submission status: Time Limit Exceeded

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


n = int(input())
routes = []
ans = [[0]*n for i in range(n)]
edges = [[]for _ in range(n)]
used = [0]*n

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

sort_routes = sorted(routes)

for node in range(n):
    unanle = used[node]
    count = 1
    if count == unanle:
        count += 1
    for to in edges[node]:
        ans[node][to] = count
        used[to] = count
        count += 1
        if count == unanle:
            count += 1

print(max(used))
for _from, to in routes:
    print(ans[_from][to])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

c = collections.Counter(vertexes)
max_color = c.most_common()[0][1]
print(max_color)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from copy import deepcopy

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

K = 0
color_set = deque([i for i in range(1, 10**5)])

q = [(0, None)]
while q:
    u, color = q.pop()
    c_set = deepcopy(color_set)
    for v in repn[u]:
        if color_dict[(u, v)] == None:
            c = c_set.popleft()
            if c != color:
                color_dict[(u, v)] = c
                color_dict[(v, u)] = c
                q.append((v, c))
            else:
                c = c_set.popleft()
                color_dict[(u, v)] = c
                color_dict[(v, u)] = c
                q.append((v, c))
            K = max(K, c)

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

Submission status: Time Limit Exceeded

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

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

def dfs(u,t,c):
  CU = set()
  if t > 0:
    CE[(min(u,t),max(u,t))] = c
    CU.add(c)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] != 0:
      CU.add(CE[(min(u,v),max(u,v))])
  CC = set()
  for cc in range(1,maxc+1):
    if cc not in CU:
      CC.add(cc)
  for v in V[u]:
    if CE[(min(u,v),max(u,v))] == 0:
      dfs(v,u,CC.pop())

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
V = [[] for _ in range(N)]
E = dict()
yobidasi = []
for i in range(N - 1):
	a, b = map(int, input().split())
	V[a - 1].append(b - 1)
	V[b - 1].append(a - 1)
	yobidasi.append([a - 1, b - 1])
	E[a - 1, b - 1] = -1
	
color_num = 0
for i in range(N):
	color_num = max(color_num, len(V[i]))

visited = [False for _ in range(N)]
Q = [[0, 0]]
print(color_num)

while Q:
	cur, parent_color = Q.pop(0)
	visited[cur] = True
	color_lst = [n for n in range(1, color_num + 1)]
	if parent_color != 0: 
		color_lst.pop(parent_color - 1)
	for adj in V[cur]:
		if visited[adj] == False:
			# print("paint")
			color = color_lst.pop(0)
			E[min(adj, cur), max(adj, cur)] = color
			Q.append([adj, color])
			
for i in range(N - 1):
	print(E[yobidasi[i][0], yobidasi[i][1]])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[set(i for i in range(1,N+1)) for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = graph[i]&graph[j]
    a_list.append(min(ans))
    graph[i].remove(min(ans))
    graph[j].remove(min(ans))
print(max(a_list))
for i in a_list:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
anslist = [[0]*N for i in range(N)]
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			anslist[i][j] = kk
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

ans = []
for ai, bi in ab:
	ans.append(anslist[ai-1][bi-1])

print(K,*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
n_list = [[] for _ in range(n+1)]
l_list = [0 for _ in range(n-1)]
for i in range(n-1):
    a,b = [int(_) for _ in input().split()]
    n_list[a].append((b,i))
    n_list[b].append((a,i))
# print(n_list)
k = 0
for i in range(n+1):
    k = max(k, len(n_list[i]))
# print(k)
c_list = []
for i in range(1, k+1):
    c_list.append(i)
# print(c_list)
todo = [(1,0)]
seen = [1]
while len(todo) != 0:
    p_from, c_from = todo.pop()
    i = 0
    for t in n_list[p_from]:
        p, l = t
        if p in seen:
            continue
        else:
            while c_list[i] == c_from:
                i += 1
            color = c_list[i]
            i += 1
            todo.append((p,color))
            l_list[l] = color
            seen.append(p)
    # print(todo)
    # print(seen)
# print(l_list)
print(k)
for i in l_list:
    print(i)

Submission status: Time Limit Exceeded

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

N = int(input())

A = [0]*N
L = [[0 for i in range(N)]for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    for j in range(1, N+1):
        if L[a-1][j-1] == 0 and L[b-1][j-1] == 0:
            L[a-1][j-1]=1
            L[b-1][j-1]=1
            A[i] = j
            break


print(max(A))
for i in range(N-1):
    print(A[i])

Submission status: Time Limit Exceeded

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


sys.setrecursionlimit(1000000)


def coloring(tree, edge_colors, now=1, parent_color=0, use_color=0):
    color = 1 if parent_color != 1 else 2
    for child in tree[now]:
        use_color = max(color, use_color)
        edge_colors[now][child] = color
        cuse_color = coloring(tree, edge_colors, child, color, use_color)
        use_color = max(use_color, cuse_color)
        color += 1 if color + 1 != parent_color else 2
    return use_color


n = int(input())
edge = []
tree = [[] for _ in range(n+1)]
edge_colors = [[0] * (n+1) for _ in range(n+1)]

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

use_color = coloring(tree, edge_colors)
print(use_color)
for a, b in edge:
    print(edge_colors[a][b])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
edge=[tuple(i for i in list(map(int,input().split(" ")))) for i in range(N-1)]
graph=[[i for i in range(1,N+1)] for j in range(N+1)]
a_list=[]
for i,j in edge:
    ans = set(graph[i])&set(graph[j])
    a_list.append(min(ans))
    graph[i].remove(min(ans))
    graph[j].remove(min(ans))
print(max(a_list))
for i in a_list:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
each_edge = [set() for i in range(N)]
ans = []
kouho = set([i+1 for i in range(N)])
for i in range(N-1):
    a, b = map(int, input().split())
    if not each_edge[a-1] and not each_edge[b-1]:
        tmp = 1
    else:
        aset = each_edge[a-1]
        bset = each_edge[b-1]
        tmp = sorted(list(kouho.difference(aset | bset)))[0]
    each_edge[a-1].add(tmp)
    each_edge[b-1].add(tmp)
    ans.append(tmp)
K = -1
for i in each_edge:
    K = max(K, len(i))
print(K)
for line in ans:
    print(line)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

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

for ai, bi in ab:
    graph[ai - 1].append(bi - 1)
    graph[bi - 1].append(ai - 1)

from collections import deque

ans = []
col_max = 1
q = deque([(0, -1, 0)])
while len(q) > 0:
    col = 1
    src, prev, col_prev = q.popleft()
    # print("#", src)
    for dst in graph[src]:
        if dst == prev: continue
        #
        if col == col_prev: col += 1
        # print("##", dst)
        # ans[src][dst] = col
        ans.append((dst, src, col))
        q.append((dst, src, col))
        col_max = max(col, col_max)
        col += 1
        
ans.sort(key=lambda x: x[0] * N + x[1])
        
print(col_max)
for ai, bi in ab:
    l = 0
    r = N - 2
    # print("#", ai, bi)
    while l < r:
        m = l + (r - l + 1) // 2
        tmp = ans[m][0] * N + ans[m][1]
        # print("#", (l, r), m, tmp)
        if tmp <= (bi - 1) * N + (ai - 1):
            l = m
        else:
            r = m - 1
    #
    # print("#", l, ans)
    print(ans[l][2])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ABs = []
for i in range(N - 1):
    ABs.append(tuple(map(int, input().split())))

Cs = [0] * (N + 1)
for i in range(N - 1):
    Cs[ABs[i][0]] += 1
    Cs[ABs[i][1]] += 1
K = max(Cs)
print(K)

ABsc = [[False] * (K + 1) for _ in range(N + 1)]
Tr = [[] for _ in range(N + 1)]
for i in range(N - 1):
    p = min(ABs[i][0], ABs[i][1])
    c = max(ABs[i][0], ABs[i][1])
    Tr[p].append((c, i))
import collections

d = collections.deque()
d.append(1)


def minC(i):
    for j in range(1, K + 1):
        if not ABsc[i][j]:
            return j


Cis = [1] * N
while (len(d) > 0):
    p = d.popleft()
    for (c, i) in Tr[p]:
        d.append(c)
        col = minC(p)
        ABsc[p][col] = True
        ABsc[c][col] = True
        Cis[i] = col

for i in range(N - 1):
    print(Cis[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [0] * N
B = [0] * N
C = [0] * N
for i in range(N-1):
    A[i],B[i] = map(int,input().split())
    C[A[i]-1] += 1
    C[B[i]-1] += 1
print(max(C))
D = [0] * N
for i in range(N):
    D[i] = []
    for j in range(1,max(C)+1):
        D[i].append(j)

for i in range(N-1):
    a = A[i]-1
    b = B[i]-1
    for i in D[a]:
        if i in D[b]:
            print(i)
            D[a].remove(i)
            D[b].remove(i)
            break

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce
from collections import Counter
# from itertools import combinations as comb
# from itertools import permutations as perm
# from copy import copy
# 配列二分法アルゴリズム
# https://docs.python.jp/3/library/bisect.html
# import bisect
# 桁数指定
# print('{:.3f}'.format(X))
# from collections import defaultdict
# dic = defaultdict(lambda: ...)
# 値で辞書をソート
# sorted(dic.items(), key=lambda x:x[1])
# ヒープキュー
# https://docs.python.org/ja/3/library/heapq.html
# import heapq
# 正規表現(regular expression)のためのモジュール
# import re

import sys

sys.setrecursionlimit(10**6)


def inpl():
    return list(map(int, input().split()))


# 重複組み合わせは nHr = (n + r - 1)Cn
def cmb(n, r):
    # combination
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def gcd(a, b):
    # greatest common divisor
    while b > 0:
        a, b = b, a % b

    return a


def lcm(a, b):
    # least common multiple
    return a * b // gcd(a, b)


def dfs(visit, a):
    visit[a] = True
    for b in tmp_list[a]:
        # print("ab", a, b)
        if visit[b] is True:
            continue

        i = color[a].index(False)
        color[a][i] = True
        color[b][i] = True
        ans_c[min(a, b), max(a, b)] = i
        dfs(visit, b)

    return


N = int(input())
AB = [inpl() for i in range(N - 1)]

ans_c = {}
tmp_list = [[] for i in range(N + 1)]
for a, b in AB:
    tmp_list[a].append(b)
    tmp_list[b].append(a)

ans = max(len(a) for a in tmp_list)
color = [[False for j in range(ans)] for i in range(N + 1)]
visit = [False for i in range(N + 1)]
dfs(visit, 1)

print(ans)
for a, b in AB:
    print(ans_c[a, b] + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
N = int(input())
P = [[] for _ in range(N + 1)]
P2 = [[0] * (N + 1) for _ in range(N + 1)]
AB = []
for _ in range(N - 1):
    a, b = [int(_) for _ in input().split()]
    P[a].append(b)
    P[b].append(a)
    AB.append((a,b))
C = 0

for p in P:
    if len(p) > C:
        C = len(p)


def f(n, pre, used):
    c = 1
    for i, next_n in enumerate(P[n]):
        if pre == next_n: continue
        if c == used: c += 1
        P2[n][next_n] = c
        P2[next_n][n] = c
        f(next_n, n, c)
        c += 1


print(C)
f(1, -1, 0)
# print(P2)
for a,b in AB:
    print(P2[a][b])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from copy import deepcopy

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

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

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

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

Submission status: Time Limit Exceeded

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


main()