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: Wrong Answer

Solution code:
n = int(input())
edges_ls = [[0,0] for _ in range(n-1)]
next_color = [0] * n
ans_ls = [0] * (n-1)
for i in range(n-1):
    a,b = map(int,input().split())
    edges_ls[i] = [a-1,b-1]
    ans_ls[i] = max(next_color[a-1],next_color[b-1])
    next_color[a-1] += 1
    next_color[b-1] += 1
print(max(next_color))
for ans in ans_ls:
    print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


n=int(input())
edge=[[] for i in range(n+1)]
par=[0]*(n+1)#i番目の頂点とその親を結ぶ辺の色
par[1]=-1
col=[0]*(n-1)#i番目の辺の色
for i in range(n-1):
    a,b=mp()
    edge[a].append([a,b,i])
    edge[b].append([b,a,i])

print(edge)

que=deque([edge[1]])
while len(que):
    k=1
    q=que.popleft()
    for x,y,i in q:
        if col[i]==0:
            if k==par[x]:
                k+=1
            col[i]=k
            par[y]=k
            k+=1
            que.append(edge[y])
print(max(col))
for i in range(n-1):
    print(col[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

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

#n=8
#g=[[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
#n=6
#g=[[1, 2, 3, 4, 5], [0], [0], [0], [0], [0]]

q=deque([0])

stack=[0]
parent=[-1]*n
pc=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
    ic=0
    for v in g[state]:
        if parent[v] !=-1:
            continue
        else:
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
            ic+=1
            if ic==pc[state]:
                ic+=1
            pc[v]=ic

k=max(pc)
print(k)
for i in range(1,n):
    print(pc[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
deg = [0 for _ in range(N)]
edges = [[] for _ in range(N - 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edges[i] = [a - 1, b - 1]
    deg[a - 1] += 1
    deg[b - 1] += 1
deg_max = max(deg)

def add(arg):  return 1 + arg % deg_max

ans = [0 for _ in range(N - 1)]
usd = [[0 for _ in range(deg_max + 3)] for _ in range(N)]
temp = 0
for i in range(N - 1):
    temp = add(temp)
    a = edges[i][0]
    b = edges[i][1]
    while(usd[a][temp] == 1 and usd[b][temp] == 1):  add(temp)
    ans[i] = temp
    usd[a][temp] = 1
    usd[b][temp] = 1
print(deg_max)
for i in range(N - 1):  print(ans[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
deg = [0 for _ in range(N)]
edges = [[] for _ in range(N - 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edges[i] = [a - 1, b - 1]
    deg[a - 1] += 1
    deg[b - 1] += 1
deg_max = max(deg)

def add(arg):  return 1 + arg % deg_max

ans = [0 for _ in range(N - 1)]
usd = [[0 for _ in range(deg_max + 3)] for _ in range(N)]
temp = 0
for i in range(N - 1):
    temp = add(temp)
    a = edges[i][0]
    b = edges[i][1]
    while(usd[a][temp] == 0 and usd[b][temp]):  add(temp)
    ans[i] = temp
    usd[a][temp] = 1
    usd[b][temp] = 1
print(deg_max)
for i in range(N - 1):  print(ans[i])

Submission status: Wrong Answer

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = [0]*(n-1)
b = [0]*(n-1)
g = [[] for i in range(n)]
for i in range(n-1):
    a[i], b[i] = MAP()
    a[i] -= 1
    b[i] -= 1
    g[a[i]].append(b[i])
    g[b[i]].append(a[i])
k = 0
for x in g:
    k = max(k, len(x))
print(k)
c = [list(range(1, k+1)) for i in range(n)]
for i in range(n-1):
    for j in range(1, k+1):
        if j in c[a[i]] and j in c[b[i]]:
            ans = j
            c[a[i]].remove(j)
            c[b[i]].remove(j)
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
N = int(input())
E = [tuple(map(lambda x: int(x) - 1, sys.stdin.readline().split())) for _ in range(N - 1)]
G = [[] for _ in range(N)]
for a, b in E:
    G[a].append(b)
    G[b].append(a)

colors = [{} for _ in range(N)]
colornum = 0
todo = deque([0])
done = set()
while todo:
    p = todo.popleft()
    done.add(p)
    used_colors = set(colors[p].values())
    for np in G[p]:
        if not np in colors[p]:
            for c in range(colornum):
                if not c in used_colors:
                    colors[p][np] = c
                    used_colors.add(c)
                    break
            else:
                c = colornum
                colors[p][np] = c
                used_colors.add(c)
                colornum += 1
        if not np in done:
            todo.append(np)

print(colornum)
for a, b in E:
    print(colors[a][b] + 1)

Submission status: Wrong Answer

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    G = [[] for _ in range(N)]
    E = []
    _E = set()
    for i in range(N-1):
        a,b=mi()
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        E.append((a-1,b-1))
        _E.add((a-1,b-1))
    
    leaf = 0
    for i in range(N):
        g = G[i]
        if len(g) == 1:
            leaf = i

    stack = deque([(leaf,1,None)])
    seen = set()
    path = {x:0 for x in E}
    K = 0

    def save(edge,color):
        if edge == None: return
        
        a,b = edge
        if (a,b) in _E:
            path[(a,b)] = color
        else:
            path[(b,a)] = color




    while stack:
        current,color,edge = stack.popleft()
        seen.add(current)
        save(edge,color)
        K = max(K,color)

        i = 1
        for next in G[current]:
            if next in seen: continue
            if color == i:
                i += 1
            
            stack.append((next,i,(current,next)))
            i += 1
    
    print(K)
    for i in range(N-1):
        a,b = E[i]
        print(path[(a,b)],sep="")







if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
t=1
ans=[[] for i in range(n+1)]
aa=[]
a,b=map(int,input().split())
ans[a].append(t)
ans[b].append(t)
aa.append(t)
a1=a
m=1
for i in range(n-2):
    a,b=map(int,input().split())
    if a==a1:
        t+=1
        if t>m:
            m=t
    else:
        t=1
    while True:
        if t not in ans[a] and t not in ans[b]:
            ans[a].append(t)
            ans[b].append(t)
            aa.append(t)
            a1=a
            break
        else:
            t+=1
            if t>m:
                m=t
print(m)
for i in aa:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy


def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    n = getN()
    graph = [[] for i in range(n)]
    ji = [0 for i in range(n)]
    hen = [0 for i in range(n-1)]
    used = [dict() for i in range(n)]
    for i in range(n - 1):
        a, b = getZList()
        graph[a].append([b, i])
        graph[b].append([a, i])
        ji[a] += 1
        ji[b] += 1
    mji = max(ji)
    mid = ji.index(mji)
    # print(mid)
    d = deque()
    d.append(mid)
    while(d):
        # print(d, hen)
        cur = d.pop()
        iro = 0
        for nc, np in graph[cur]:
            if hen[np] != 0:
                continue
            # print(iro)
            while True:
                if iro not in used[cur]:
                    hen[np] = iro + 1
                    iro += 1
                    d.append(nc)
                    used[nc][iro] = 1
                    break
                iro += 1


    # jiq = [(ji[i], i) for i in range(n)]
    # jiq.sort(reverse=True)
    # for _, id in jiq:
    #     iro = 0
    #     for tg, he in graph[id]:
    #         # for iro in range(mji):
    #         if hen[he] != 0:
    #             continue
    #         while True:
    #             if iro not in used[id]:
    #                 hen[he] = iro+1
    #                 used[tg][iro] = 1
    #                 iro += 1
    #                 break
    #             iro += 1

    print(mji)
    print(*hen, sep="\n")



def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy


def soinsu(n):
    ret = defaultdict(int)
    for i in range(2, int(math.sqrt(n) + 2)):
        if n % i == 0:
            while True:
                if n % i == 0:
                    ret[i] += 1
                    n //= i
                else:
                    break

    if not ret:
        return {n: 1}
    return ret


def solve():
    n = getN()
    graph = [[] for i in range(n)]
    ji = [0 for i in range(n)]
    hen = [0 for i in range(n-1)]
    used = [dict() for i in range(n)]
    for i in range(n - 1):
        a, b = getZList()
        graph[a].append([b, i])
        graph[b].append([a, i])
        ji[a] += 1
        ji[b] += 1
    mji = max(ji)
    jiq = [(ji[i], i) for i in range(n)]
    jiq.sort(reverse=True)
    for _, id in jiq:
        iro = 0
        for tg, he in graph[id]:
            # for iro in range(mji):
            if hen[he] != 0:
                continue
            while True:
                if iro not in used[id]:
                    hen[he] = iro+1
                    used[tg][iro] = 1
                    iro += 1
                    break
                iro += 1

    print(mji)
    print(*hen, sep="\n")



def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
s = input()
x = 7
if s == "SUN":
    pass
elif s == "SAT":
    x = x - 6
elif s == "FRI":
    x = x - 5
elif s == "THU":
    x = x - 4
elif s == "WED":
    x = x - 3
elif s == "TUE":
    x = x - 2
elif s == "MON":
    x = x - 1


print(x)

Submission status: Wrong Answer

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

n = int(input())

ab = []
adj = [[] * (n+1) for _ in range(n+1)]

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

m = [0] * (n+1)
for a, b in ab:
    m[a] += 1
    m[b] += 1

k = max(m)
print(k)

visited = [False] * (n+1)
label = [(0, 0)] * (n+1)

q = deque([i])
visited[i] = True
while len(q) > 0:
    v = q.popleft()
    l = 0
    for w in adj[v]:
        if not visited[w]:
            l += 1
            if label[v][1] == l:
                l += 1
            label[w] = (v, l)
            visited[w] = True
            q.append(w)

for a, b in ab:
    if label[a][0] == b:
        print(label[a][1])
    else:
        print(label[b][1])

Submission status: Wrong Answer

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

n = int(input())

ab = []

for i in range(n-1):
    ab.append(list(map(int, input().split())))

m = [0] * (n+1)
for a, b in ab:
    m[a] += 1
    m[b] += 1

l = max(m)
print(l)

used = [[False] * (l + 1) for _ in range(n+1)]

for a, b in ab:
    for j in range(1, l+1):
        if (not used[a][j]) and (not used[b][j]):
            print(j)
            used[a][j] = True
            used[b][j] = True
            break

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    edge[(a, b)] = i
    graph[a].append(b)
    graph[b].append(a)
graph2 = [[] for i in range(n - 1)]
flag = [False for i in range(n - 1)]
queue = collections.deque([list(edge.keys())[0]])
while queue:
    temp = queue.popleft()
    num = edge[temp]
    if flag[num] == True:
        continue
    flag[num] = True
    node1 = temp[0]
    node2 = temp[1]
    for i in graph[node1]:
        node3, node4 = min(i, node1), max(i, node1)
        num2 = edge[(node3, node4)]
        if flag[num2] == False:
            graph2[num].append(num2)
            graph2[num2].append(num)
            queue.append((node3, node4))
    for i in graph[node2]:
        node3, node4 = min(i, node2), max(i, node2)
        num2 = edge[(node3, node4)]
        if flag[num2] == False:
            graph2[num].append(num2)
            graph2[num2].append(num)
            queue.append((node3, node4))
color = [None for i in range(n - 1)]
color[0] = 1
queue = collections.deque([[0, 1]])
while queue:
    temp = queue.popleft()
    num = temp[0]
    col = temp[1]
    temp2 = 1
    for i in graph2[num]:
        if color[i] != None:
            continue
        else:
            if temp2 == col:
                color[i] = temp2 + 1
                temp2 += 2
            else:
                color[i] = temp2
                temp2 += 1
            queue.append([i, color[i]])
print(max(color))
for i in range(n - 1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
graph = [[] for i in range(n + 1)]
edge = {}
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    edge[(a, b)] = i
    graph[a].append(b)
    graph[b].append(a)
graph2 = [[] for i in range(n - 1)]
flag = [False for i in range(n - 1)]
queue = collections.deque([list(edge.keys())[0]])
while queue:
    temp = queue.popleft()
    num = edge[temp]
    if flag[num] == True:
        continue
    flag[num] = True
    node1 = temp[0]
    node2 = temp[1]
    for i in graph[node1]:
        node3, node4 = min(i, node1), max(i, node1)
        num2 = edge[(node3, node4)]
        if flag[num2] == False:
            graph2[num].append(num2)
            graph2[num2].append(num)
            queue.append((node3, node4))
    for i in graph[node2]:
        node3, node4 = min(i, node2), max(i, node2)
        num2 = edge[(node3, node4)]
        if flag[num2] == False:
            graph2[num].append(num2)
            graph2[num2].append(num)
            queue.append((node3, node4))
color = [None for i in range(n - 1)]
flag = [False for i in range(n - 1)]
color[0] = 1
queue = collections.deque([[0, 1]])
while queue:
    temp = queue.popleft()
    num = temp[0]
    col = temp[1]
    flag[num] = True
    temp2 = 1
    for i in graph2[num]:
        if color[i] != None:
            continue
        else:
            if temp2 == col:
                color[i] = temp2 + 1
                temp2 += 2
            else:
                color[i] = temp2
                temp2 += 1
            queue.append([i, color[i]])
print(max(color))
for i in range(n - 1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**9)


def dfs(s, to, seen, sides, color, palette, i=0):
    seen[s] = 1
    for v in to[s]:
        if seen[v]:
            continue
        if s < v:
            color[f'{s}'+f'{v}'] = palette[i % len(palette)]
            i += 1
        dfs(v, to, seen, sides, color, palette, i)


def solve():
    N = int(input())
    sides = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N - 1)]
    to = [[] for _ in range(N)]
    for a, b in sides:
        to[a].append(b)
        to[b].append(a)
    colors_used = max(len(sub) for sub in to)
    palette = [i for i in range(1, colors_used+1)]
    seen = [0] * N
    color = {f'{a}'+f'{b}':0 for a, b in sides}

    dfs(0, to, seen, sides, color, palette)

    print(colors_used)
    print(*[color[f'{a}' + f'{b}'] for a, b in sides], sep='\n')


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**9)


def dfs(s, to, color, palette, i=0):
    seen[s] = 1
    for v in to[s]:
        if seen[v]:
            continue
        if s < v:
            color[f'{s}'+f'{v}'] = palette[i % len(palette)]
            i += 1
        dfs(v, to, color, palette, i)


N = int(input())
sides = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N - 1)]
to = [[] for _ in range(N)]
for a, b in sides:
    to[a].append(b)
    to[b].append(a)
colors_used = max(len(sub) for sub in to)
palette = [i for i in range(1, colors_used+1)]
seen = [0] * N
color = {f'{a}'+f'{b}':0 for a, b in sides}

dfs(0, to, color, palette)

print(colors_used)
print(*[color[side] for side in sorted(color.keys())], sep='\n')

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**9)


def dfs(s, to, color, palette, i=0):
    seen[s] = 1
    for v in to[s]:
        if seen[v]:
            continue
        if s < v:
            color[f'{s + v}'] = palette[i % len(palette)]
            i += 1
        dfs(v, to, color, palette, i)


N = int(input())
sides = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N - 1)]
to = [[] for _ in range(N)]
for a, b in sides:
    to[a].append(b)
    to[b].append(a)
colors_used = max(len(sub) for sub in to)
palette = [i for i in range(1, colors_used+1)]
seen = [0] * N
color = {f'{a + b}':0 for a, b in sides}

dfs(0, to, color, palette)

print(colors_used)
print(*[color[side] for side in sorted(color.keys())], sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])
#print(tree)
while Q:
  temp = Q.popleft()
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now == col[temp]:
      now += 1
    col[n] = now
    now += 1
    Q.append(n)
    
print(m)
for v in col[2:]:
  print(v)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])
#print(tree)
while Q:
  temp = Q.popleft()
  pre = col[temp]
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now!=pre:
      col[n]=now
      now += 1
    else:
      col[n]=now+1
      now += 2
    #print(n,now)
    Q.append(n)
    
print(m)
for v in col[2:]:
  print(v)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])
#print(tree)
while Q:
  temp = Q.popleft()
  pre = col[temp]
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now!=pre:
      col[n]=now
      now += 1
    else:
      col[n]=now+1
      now += 2
    #print(n,now)
    Q.append(n)
    
print(m,*col[2:])

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
m = len(max(tree,key=len))
col = [0]*(n+1)
Q = deque([1])

while Q:
  temp = Q.popleft()
  pre = col[temp]
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now!=pre:
      col[n]=now
      now += 1
    else:
      col[n]=now+1
      now += 2
    Q.append(n)
    
print(m,*col[2:])

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
m = len(max(tree,key=len))
col = [0]*(n+1)
Q = deque([1])
print(tree)
while Q:
  temp = Q.popleft()
  pre = col[temp]
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now!=pre:
      col[n]=now
      now += 1
    else:
      col[n]=now+1
      now += 2
    Q.append(n)
    
print(m,*col[2:])

Submission status: Wrong Answer

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

k=0
for i in range(n):
    k=max(k, len(G[i]))
print(k)
color=[[0]*k for _ in range(n)]

for A, B in edge:
    for i in range(k):
        if color[A][i]+color[B][i]==0:
            color[A][i]+=1
            color[B][i]+=1
            print(i+1)
            break

Submission status: Wrong Answer

Solution code:
import sys

from itertools import chain
def input(): return sys.stdin.readline().rstrip()


def edge(x, y):
    z = x | y
    for i in range(1, len(z)+3):
        if i not in z:
            return i


def main():
    n = int(input())
    edges = [[] for _ in range(n-1)]
    colors = [set() for _ in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        edges[i] = [a, b]
    ans = 1
    anss = [0]*(n-1)
    for i in range(n-1):
        nowcolor = edge(colors[edges[i][0]], colors[edges[i][0]])
        colors[edges[i][0]].add(nowcolor)
        colors[edges[i][1]].add(nowcolor)
        if nowcolor > ans:
            ans=nowcolor
        anss[i]=nowcolor
    print(ans)
    for i in range(n-1):
        print(anss[i])
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import os
import sys
from collections import defaultdict
adj = defaultdict(list)
col = defaultdict(int)
sys.setrecursionlimit(1000000)
mx=0
edges = {}
def find_color(u , p):
	global mx , now
	cnt =0
	for i in adj[u]:
		cnt = cnt+1
		if i==p:
			continue
		find_color(i , u)
	mx = max(mx, cnt)
now =0
def dfs(u , p):
	global mx, now
	for i in adj[u]:
		if i==p:
			continue
		col[edges[i,u]]=now
		now =(now+1)%mx
	for i in adj[u]:
		if i==p:
			continue
		dfs(i , u)

def main():
	n = int(input())
	for i in range(n-1):
		x, y = map(int , input().split())
		adj[x].append((y))
		adj[y].append((x))
		edges[x,y]=i
		edges[y,x]=i
	find_color(1, 0)
	dfs(1, 0)
	print(mx)
	for i in range(n-1):
		print(col[i]+1)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d=[set() for _ in range(N)]
c=[]
if N>2:
  for i in range(N-1):
    x,y = (int(r) for r in input().rstrip('\n').split())
    cm = d[x-1]|d[y-1]
    for m in range(N):
      if m not in cm:
        c.append(m)
        d[x-1].add(m)
        d[y-1].add(m)
        break
  print(max(c)+1)
  for a in c:
    print(a+1)
else:
  print(1)
  print(1)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d=[set() for _ in range(N)]
c=[]
if N>2:
  for i in range(N-1):
    x,y = (int(r) for r in input().rstrip('\n').split())
    cm = d[x-1]|d[y-1]
    for m in range(len(cm)+1):
      if m==len(cm):
        c.append(m)
        d[x-1].add(m)
        d[y-1].add(m)
      else:
        if m not in cm:
          c.append(m)
          d[x-1].add(m)
          d[y-1].add(m)
          break
  print(max(c)+1)
  for a in c:
    print(a+1)
else:
  print(1)
  print(1)

Submission status: Wrong Answer

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

N=int(input().rstrip('\n'))
d=[set() for _ in range(N)]
c=[]
if N>2:
  for i in range(N-1):
    x,y = (int(r) for r in input().rstrip('\n').split())
    cm = d[x-1]|d[y-1]
    for m in range(N+1):
      if m not in cm:
        c.append(m)
        d[x-1].add(m)
        d[y-1].add(m)
        break
  print(max(c)+1)
  for a in c:
    print(a+1)
else:
  print(1)
  print(1)