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:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
from collections import defaultdict
import sys
def zz():
    return list(map(int, sys.stdin.readline().split()))
def z():
    return int(sys.stdin.readline())
n = z()
a = [0] * (n)
b = [0] * (n)
dim_lis = [0]*n
G = [[] for _ in range(n)]
for i in range(n-1):
    a, b = zz()
    dim_lis[a - 1] += 1
    dim_lis[b - 1] += 1
    G[a-1].append((b-1, i))
    G[b-1].append((a-1, i))
# G = sorted(G)

max_node = np.argmax(dim_lis)
max_color = dim_lis[max_node]

que = deque([max_node])
visited = [False]*n
# color = 1
ans = [0] * (n - 1)
colors = defaultdict(list) 
while que:
    # print(len(que))
    color = 1
    node = que.pop()
    visited[node] = True
    for to, edge in G[node]:
        if (ans[edge] == 0):
            while (color in colors[node]):
                color += 1                
            ans[edge] = color
            colors[node].append(color)
            colors[to].append(color)
        # color = (color % max_color) + 1
        if (not visited[to]):
            que.append(to)
print(max_color)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
import collections
from collections import defaultdict

mod = 10 ** 9 + 7
n = int(input())
a = [0] * (n)
b = [0] * (n)
dim_lis = [0]*n
G = [[] for _ in range(n)]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    dim_lis[a - 1] += 1
    dim_lis[b - 1] += 1
    G[a-1].append((b-1, i))
    G[b-1].append((a-1, i))
# G = sorted(G)

max_node = np.argmax(dim_lis)
max_color = dim_lis[max_node]

que = deque([max_node])
visited = [False]*n
color = 1
ans = [0] * (n - 1)
colors = defaultdict(list) 
while que:
    # print(len(que))
    node = que.pop()
    visited[node] = True
    for to, edge in G[node]:
        if (ans[edge] == 0):
            while (color in colors[node]):
                color = (color % max_color) + 1                
            ans[edge] = color
            colors[node].append(color)
            colors[to].append(color)
        color = (color % max_color) + 1
        if (not visited[to]):
            que.append(to)
print(max_color)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
input = sys.stdin.readline

n = int(input())
x = [[0 for _ in range(n - 1)] for _ in range(n)]
colors = set()
ans = []
for i in range(n - 1):
    a, b = map(int, input().split())
    if len(colors) == 0:
        x[a - 1][0] = 1
        x[b - 1][0] = 1
        ans.append(1)
        colors.add(0)
        continue
    flag = True
    c = 0
    for j in colors:
        c = max(c, j)
        if x[a - 1][j] == 0 and x[b - 1][j] == 0:
            flag = False
            x[a - 1][j] = 1
            x[b - 1][j] = 1
            ans.append(j + 1)
            break
    if flag:
        x[a - 1][c + 1] = 1
        x[b - 1][c + 1] = 1
        ans.append(c + 2)
        colors.add(c + 1)
print(len(colors))
for i in ans:
    print(i)


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

# x = [[0 for _ in range(n - 1)] for _ in range(n)]
# ans = []
# cnt = [0 for i in range(n - 1)]
# ans_set = set()
# a_append = ans.append
# for i in range(n - 1):
#     for j in range(n - 1):
#         if x[a[i] - 1][j] == x[b[i] - 1][j] == 0:
#             x[a[i] - 1][j] = 1
#             x[b[i] - 1][j] = 1
#             a_append(j + 1)
            
#             cnt[j] = 1
#             break
# print(cnt.count(1))
# for i in ans:
#     print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
input = sys.stdin.readline

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

x = [[0 for _ in range(n - 1)] for _ in range(n)]
ans = []
cnt = [0 for i in range(n - 1)]
a_append = ans.append
for i in range(n - 1):
    for j in range(n - 1):
        if x[a[i] - 1][j] == x[b[i] - 1][j] == 0:
            x[a[i] - 1][j] = 1
            x[b[i] - 1][j] = 1
            a_append(j + 1)
            cnt[j] = 1
            break
print(cnt.count(1))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n = int(input())
a = [0 for _ in range(n - 1)]
b = [0 for _ in range(n - 1)]
for i in range(n - 1):
    a[i], b[i] = map(int, input().split())

x = [[0 for _ in range(n - 1)] for _ in range(n)]
ans = []
for i in range(n - 1):
    for j in range(n - 1):
        if x[a[i] - 1][j] == x[b[i] - 1][j] == 0:
            x[a[i] - 1][j] = 1
            x[b[i] - 1][j] = 1
            ans.append(j + 1)
            break
print(len(set(ans)))
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
matrix= []
lis = [[] for i in range(n)]
ans = [[0 for i in range(n)] for j in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    matrix.append(sorted([a,b]))
    lis[a].append(b)
    lis[b].append(a)
color = [-1 for _ in range(n)]
queue = deque([0])
color[0] = 1001001001
maxc = 0
while len(queue) > 0:
    now = queue.pop()
    used = color[now]
    tmp = 1
    for i in lis[now]:
        if color[i] == -1:
            queue.append(i)
            if tmp == used:
                tmp += 1
            color[i] = tmp
            ans[now][i] = tmp
            ans[i][now] = tmp
            maxc = max(maxc, tmp)
            tmp += 1
print(maxc)
for i in range(n-1):
    root = matrix[i]
    print(ans[root[0]][root[1]])

Submission status: Time Limit Exceeded

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

settansaku = set([])
setmada = {0}
listmada = [(0, None)]  #left: Vertex, right: Color
kouho = 1
num = [0 for _ in range(n-1)]

while kouho != 0:
	for i, cnt in listmada[:]:
		colors = {cnt}
		settansaku.add(i)
		setmada.remove(i)
		listmada.remove((i, cnt))
		kouho -= 1
		for k, j in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					c = 0
					while True:
						if c not in colors:
							listmada.append((k, c))
							colors.add(c)
							num[j] = c
							break
						c += 1
					kouho += 1

print(max(num)+1)
print("\n".join([str(i+1) for i in num]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
color=[[-1 for j in range(n)] for i in range(n)]
res=[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  for j in range(n):
    if color[a-1][j]<0 and color[b-1][j]<0:
      color[a-1][j]=i
      color[b-1][j]=i
      res[i]=j+1
      break
  else:
    assert 0
print(max(res))
for i in range(n-1):
  print(res[i])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d

"""
import sys


from collections import OrderedDict, deque

def main(args):
    N = int(input())
    G = [[] for _ in range(N+1)]
    res = OrderedDict()
    for _ in range(N-1):
        a, b = map(int, input().split())
        res[(a, b)] = -1
        G[a].append(b)
        G[b].append(a)

    k = max(len(g) for g in G)
    colors = [set(range(1, k+1)) for _ in range(N+1)]
    q = deque([1])
    visited = set([1])
    while q:
        cn = q.popleft()
        for nn in G[cn]:
            if nn not in visited:
                visited.add(nn)
                q.append(nn)
                c = min(colors[cn])
                colors[cn].discard(c)
                colors[nn].discard(c)
                if (cn, nn) in res:
                    res[(cn, nn)] = c
                if (nn, cn) in res:
                    res[(nn, cn)] = c
    print(k)
    for v in res.values():
        print(v)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

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

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()
    cand = [i+1 for i in range(max_len)]
    current_colors = [colors[p[0]] for p in mat[current] if colors[p[0]] > 0]
    for col in current_colors:
        cand.remove(col)

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        col = cand.pop()
        colors[p[0]] = col
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

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

q = []
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.pop()
    cand = [i+1 for i in range(max_len)]
    current_colors = [colors[p[0]] for p in mat[current] if colors[p[0]] > 0]
    for col in current_colors:
        cand.remove(col)

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        col = cand.pop()
        colors[p[0]] = col
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)

Submission status: Time Limit Exceeded

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

from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用色リスト
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
    maxi=max(maxi,len(d[a[i]-1]),len(d[b[i]-1]))

v=deque([0])
e[0]=0
all=set(i+1 for i in range(maxi) )

while len(v)>0:
  k=v.popleft()
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=pos.pop()
      c[k].add(s)
      c[item].add(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
    
print(maxi)
for i in range(N-1):
  t_str = str(a[i]-1)+","+str(b[i]-1)
  print(di[t_str])

Submission status: Time Limit Exceeded

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

from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用色リスト
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
    maxi=max(maxi,len(d[a[i]-1]),len(d[b[i]-1]))

v=deque([0])
e[0]=0
all=set(i+1 for i in range(maxi) )

while len(v)>0:
  k=v.popleft()
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
    
print(maxi)
for i in range(N-1):
  t_str = str(a[i]-1)+","+str(b[i]-1)
  print(di[t_str])

Submission status: Time Limit Exceeded

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

input=sys.stdin.readline
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

maxi=0
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
    maxi=max(maxi,len(d[a[i]-1]),len(d[b[i]-1]))

v=deque([0])
e[0]=0

while len(v)>0:
  k=v.popleft()
  all=set(i+1 for i in range(maxi) )
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
    
print(maxi)
for i in range(N-1):
  t_str = str(a[i]-1)+","+str(b[i]-1)
  print(di[t_str])

Submission status: Time Limit Exceeded

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

input=sys.stdin.readline
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
      
print(maxi)
for i in range(N-1):
  t_str = str(a[i]-1)+","+str(b[i]-1)
  print(di[t_str])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
f=deepcopy(d)

v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
      
print(maxi)
for i in range(N-1):
  t_str = str(a[i]-1)+","+str(b[i]-1)
  print(di[t_str])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)
f=deepcopy(d)
#print(f)

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      g[k][item]=s
      g[item][k]=s
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import heapq
n=int(input())
rel=defaultdict(set)
colrel=defaultdict(int)
cols=defaultdict(set)
p=[list(map(int,input().split())) for _ in range(n-1)]
for a,b in p:
  rel[a].add(b)
  rel[b].add(a)

m=0
for l in rel.values():
  m=max(len(l),m)

visited=set([1])
cand=deque([1])
while len(cand)!=0:
  now=cand.popleft()
  for i in rel[now]:
    if not i in visited:
      cand.append(i)
      visited.add(i)
      uni=cols[now]|cols[i]
      tmp=list(set(range(1,m+1))-uni)
      heapq.heapify(tmp)
      c=heapq.heappop(tmp)
      colrel[(min(now,i),max(now,i))]=c
      cols[now].add(c)
      cols[i].add(c)
      
ans=[colrel[(min(a),max(a))] for a in p]
print(m)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      g[k][item]=s
      g[item][k]=s
      v.append(item)
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      g[k][item]=s
      g[item][k]=s
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )