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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m>mxd:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
                dc[(c,i)]=col
            col+=1
    return

bfs(mxi)
print(mxd)
for i,j in c:
    print(dc[(i,j)]+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = [0]*N
ape = [set() for _ in range(N)]
hen = [0]*(N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    hen[i] = max(tree[a-1], tree[b-1])
    print(hen[i])
    while True:
        if (hen[i] in ape[a-1]) or (hen[i] in ape[b-1]):
            hen[i] -= 1
        else:
            break
    ape[a-1].add(hen[i])
    ape[b-1].add(hen[i])
    tree[a-1] += 1
    tree[b-1] += 1
ma = max(tree)
print(ma)
for i in range(N-1):
    print(hen[i]+1)

Submission status: Wrong Answer

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    G = [[] for k in range(N)]
    T = []
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        T.append([a,b])
    P = [0 for k in range(N)]
    for k in range(N):
        P[k] = len(G[k])
    print(max(P))
    C = [set([]) for k in range(N+1)]
    ans = []
    for e in T:
        t = 1
        while t in C[e[0]] or t in C[e[1]]:
            t += 1
        print(t)
        C[e[0]].add(t)
        C[e[1]].add(t)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)


class Node:

    def __init__(self, _id):
        self.id = _id
        self.children = []
        self.color = None

    def add(self, node):
        self.children.append(node)

    def __len__(self):
        return len(self.children)

    def coloring(self):
        if not self.children:
            return
        for i, child in enumerate(self.children):
            if i < self.color or self.color == -1:
                child.color = i
                child.coloring()
            else:
                child.color = i+1
                child.coloring()


def main():
    n = int(input())

    nodes = [Node(i) for i in range(n)]

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

    nodes[0].color = -1
    nodes[0].coloring()
    del nodes[0]

    print(max([n.color for n in nodes])+1)
    for n in nodes:
        print(n.color+1)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*(N-1)
b = [0]*(N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
ColorV = [0]*(N)
ab = [[0,0] for _ in range(N-1)]
for i in range(N-1):
    ab[i][0] = a[i]
    ab[i][1] = b[i]

ab.sort()
L = []
n = 1
maxn = 1

for i in range(N-1):
    if i == 0:
        ColorV[0] = 0
        ColorV[1] = 1
        L.append(1)
    else:
        if ab[i][0] == ab[i-1][0]:
            if n + 1 != ColorV[ab[i][0]-1]:
                ColorV[ab[i][1]-1] = n+1
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
            else:
                ColorV[ab[i][1]-1] = n+2
                L.append(n+2)
                n = n+2
                if n >= maxn:
                    maxn = n
        else:
            n = 1
            if n != ColorV[ab[i][0]-1]:
                ColorV[ab[i][1]-1] = n
                L.append(n)
                if n >= maxn:
                    maxn = n
            else:
                ColorV[ab[i][1]-1] = n+1
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
print(maxn)
for i in range(N-1):
    print(L[i])

Submission status: Wrong Answer

Solution code:
n=int(input())

nodes=[0]*n
ans=[]
for i in range(n-1):
    a,b=list(map(int, input().split()))
    nodes[a-1]+=1
    nodes[b-1]+=1
    ans.append(max(nodes[a-1],nodes[b-1]))

print(max(nodes))
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import deque 
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

tree = [[] for _ in range(N)] 
number = [[] for _ in range(N)]
color = [[] for _ in range(N - 1)]

tree_deq = deque()

for i in range(N - 1):
    tree[AB[i][0] - 1].append(AB[i][1] - 1)
    tree[AB[i][1] - 1].append(AB[i][0] - 1)


que = deque([[0, -1, -1]])
while len(que) > 0:
    node, parent, parent_color = que.pop()
    color_No = 1
    # 現在の節から繋がっている節を全て確認
    for child in tree[node]:
        if child == parent:
            continue
        if color_No == parent_color:
            color_No += 1
        color[child - 1] = color_No
        que.appendleft([child, node, color_No])
        color_No += 1

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

Submission status: Wrong Answer

Solution code:
import math
import os
import sys
from collections import deque
# from fractions import gcd
input = sys.stdin.readline

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    graph = [[] for i in range(N+1)]
    colors = [-1] * (N + 1)

    graph[0] = [1]
    graph[1].append(0)
    for i in range(N-1):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    # print(graph)

    q = deque()
    q.append(0)
    visited = [False] * (N + 1)
    visited[0] = True
    colors[0] = 1
    colors[1] = 1
    # colors[1] = 1
    # print('====================')

    while len(q) != 0:
        nxtIdx = q.popleft()
        nxt = graph[nxtIdx]
        ava = [i for i in range(1, len(nxt) * 2)]
        used = {}
        for e in nxt:
            if colors[e] != -1:
                used[colors[e]] = True
            # ncolors.append((e, colors[e]))

        # print(ncolors)
        # print(used)
        # print(ava)
        # print(nxt, used, ava)

        for e in nxt:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                # print(idx, e)
                while len(ava) != 0:
                    color = ava.pop(0)
                    if color not in used:
                        # print('p', 'e' , e, 'color', color)
                        colors[e] = color
                        break

        # print('====================')

    for i in range(1, len(colors)):
        print(colors[i])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

N = int(input())
adj = [set() 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].add(b)
    adj[b].add(a)
    ed.append([a, b])

col = max(len(v) for v in adj)

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

Q = [[s, -1, -1]]
while Q:
    cur, prev, NG = Q.pop()
    c = 1
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == NG:
            c += 1
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[a*N + b])

Submission status: Wrong Answer

Solution code:
n = int(input())
e = [list(map(int, input().split())) for _ in range(n-1)]
c = [0 for _ in range(n-1)]
e.sort()
cl = [set() for _ in range(n)]

itr = 0
for i in range(n-1):
    try:
        while(1):
            if e[itr][0]-1 == i:
                cn = 1
                while(1):
                    if cn in cl[i]:
                        cn+=1
                    else:
                        break
                c[itr] = cn
                cl[e[itr][0]-1].add(cn)
                cl[e[itr][1]-1].add(cn)
                itr+=1
            else:
                break
    except:
        pass
    



print(max(c))
for num in c:
    print(num)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]
edges.sort()

used = [set() for i in range(N+1)]
answer = []

for a, b in edges:
    cur = 1
    s = used[a] | used[b]
    while cur in s:
        cur += 1
    answer.append(cur)
    used[a].add(cur)
    used[b].add(cur)

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    lines = [list(map(int, input().split())) for i in range(N-1)]

    lines.sort()

    nodes = [[] for i in range(N)]

    for l in lines:

        nodes[l[0]-1].append(l[1])
        nodes[l[1]-1].append(l[0])

    max = 0
    for n in nodes:
        if max < len(n):
            max = len(n)

    #色の数
    print(max)

    #関係の数字
    a,b = lines[0][0],lines[0][1]
    n=1

    for l in lines:

        if n == 1:
            print(n)
            n+=1
        else:

            #print(str(l[0]) + " " + str(l[1]))
            #print(str(a) + " " + str(b))

            if l[0] == a or l[0] == b:
                print(n)
                n+=1
            else:
                print(1)
                n=2
        #print("")
        a,b = l[0],l[1]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [0] * (10 ** 5 + 1)
L_ = [0] * (10 ** 5 + 1)
A = []
for i in range(N-1):
    a, b = map(int, input().split())
    A.append((a, b))
    L[a] += 1
    L[b] += 1
print(max(L))
for i in range(N - 1):
    a, b = A[i]
    print(L_[a]+L_[b]+1)
    L_[a] += 1
    L_[b] += 1

Submission status: Wrong Answer

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline


class Node:
    def __init__(self, num):
        self.num = num
        self.edge_colors = []


N = int(input())

# treeの初期化
tree = []
tree.append(Node(0))
for i in range(1, N + 1):
    tree.append(Node(i))


colors = []

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

    # edgeの１本目
    if len(colors) == 0:
        edge_color = 1
        colors.append(edge_color)
        tree[a].edge_colors.append(edge_color)
        tree[b].edge_colors.append(edge_color)
    else:
        used_colors = tree[a].edge_colors + tree[b].edge_colors
        # if len(used_colors) == 0:
        #     # その視点、終点の頂点に初めて辺が入る時
        #     edge_color = colors[0]
        #     tree[a].edge_colors.append(edge_color)
        #     tree[b].edge_colors.append(edge_color)
        # else:
        unused_colors = list(set(colors) - set(used_colors))
        if len(unused_colors) == 0:
            # 新しい色の辺を使う
            edge_color = max(colors) + 1
            colors.append(edge_color)
            tree[a].edge_colors.append(edge_color)
            tree[b].edge_colors.append(edge_color)
        else:
            # 元々あった色の辺を使う
            edge_color = unused_colors[0]
            tree[a].edge_colors.append(edge_color)
            tree[b].edge_colors.append(edge_color)

    ans.append(edge_color)

print(len(colors))
for a in ans:
    print(a)

Submission status: Wrong Answer

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


d = {}
for i in range(1, N+1):
    d[i] = []
d_lines = {}
col = [1]
n_cols = 1

d[g[0][0]].append(1)
d[g[0][1]].append(1)

d_lines[1] = [g[0][0], g[0][1]]

for gi in g[1:]:
    a, b = gi[0], gi[1]

    n = 1
    while True:
        if n not in d[a]:
            break
        else:
            n += 1
    col.append(n)
    n_cols = max(n_cols, n)
    d[a].append(n)
    d[b].append(n)

print(n_cols)
for c in col:
    print(c)

Submission status: Wrong Answer

Solution code:
def examD():
    N = I()
    cur = [0]*(N-1)
    super = [0]*(N+1)
    d = defaultdict(int)
    V = [[] for _ in range(N+1)]
    S = set(i+1 for i in range(N))
    SA = set()
    for i in range(N-1):
        A,B = LI()
        V[A].append(B)
        SA.add(B)
    start = S-SA
    s = list(start)
    que = deque()
    que.append(s[0])
    cura = 0
    while(cura<N and que):
        i = que.pop()
        for j in V[i]:
            a, b = i, j
            d[a] += 1
            if d[a] != super[a]:
                cur[cura] = d[a]
            else:
                d[a] += 1
                cur[cura] = d[a]
            super[b] = cur[cura]
            que.append(b)
            cura += 1
    ans = max(cur)
    print(ans)
    for i,v in enumerate(cur):
        print(v)

def examE():
    N, K = LI()

    return

def examF():
    return

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
import sys
from pprint import pprint

n = int(sys.stdin.readline().strip())
edges = []
for _ in range(n-1):
    edges.append(list(map(int, sys.stdin.readline().strip().split(" "))))

count = [0] * (n+1)
# pprint(edges)
pre_color = -1
colors = []

point_used = {}
for edge in edges:
    count[edge[0]] += 1
    count[edge[1]] += 1

    if edge[0] not in point_used:
        point_used[edge[0]] = [1]
        point_used[edge[1]] = [1]
        colors.append(1)
        continue
    
    for i in range(1, 10**5 + 1): 
        if i not in point_used[edge[0]]:
            point_used[edge[0]].append(i)
            if edge[1] not in point_used:
                point_used[edge[1]] = []
            point_used[edge[1]].append(i)
            colors.append(i)
            break

print(max(count))
for c in colors:
    print(c)

Submission status: Wrong Answer

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


def main():
    N = int(input().strip())
    each_edge = [set() for i in range(N)]
    ans = []

    for i in range(N-1):
        a, b = map(int, input().strip().split())
        aset = each_edge[a-1]
        bset = each_edge[b-1]
        outlist = aset | bset
        for i in range(N-1):
            if i+1 in outlist:
                continue
            else:
                tmp = i+1
                break
        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)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append([b, i])
  else:
    edges[a] = [[b, i]]
  if b in edges.keys():
    edges[b].append([a, i])
  else:
    edges[b] = [[a, i]]
colors = [0 for i in range(n-1)]
flags = [False for i in range(n+1)]
def search(node, cannot):
  i = 1
  global flags
  global colors
  global edges
  flags[node] = True
  for edge in edges[node]:
    if flags[edge[0]] == False:
      if i != cannot:
        colors[edge[1]] += i
      else:
        i += 1
        colors[edge[1]] += i
      i += 1
      search(edge[0], i-1)
try:
  search(n, 0)
except:
  print(0)
print(max(colors))
for i in range(n-1):
  print(colors[i])

Submission status: Wrong Answer

Solution code:
N = int(input())
col = [[] for _ in range(N+1)]
Num = set([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]
    for i in range(N+1):
        if i in col[left] or i in col[right]:
            continue
        else:
            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: Wrong Answer

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


def main():
    N = int(input())
    C = [set() for _ in range(N)]
    E = [[] for _ in range(N)]
    E2 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
        E2.append([a-1, b-1])
#    print(E)
#    print(E2)
    K = 0
    for e in E:
        K = max(K, len(e))
    print(K)
    for a, b in E2:
        for c in range(1, K+1):
            if c not in (C[a] | C[b]):
                print(c)
                C[a].add(c)
                C[b].add(c)
                break


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

a = [0]*(n-1)
b = [0]*(n-1)

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

knode = []
for i in range(n):
    knode.append(list(range(1,n+1)))

c = [0]*(n-1)
for i in range(n-1):
    set_a = set(knode[a[i]-1])
    set_b = set(knode[b[i]-1])
    s_union = set_a & set_b
    c[i] = s_union.pop()
    knode[a[i]-1].remove(c[i])
    knode[b[i]-1].remove(c[i])

print(max(c))
for i in c:
    print(i)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*(N-1)
b = [0]*(N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
ColorV = [0]*(N)
ab = [[0,0] for _ in range(N-1)]
for i in range(N-1):
    ab[i][0] = a[i]
    ab[i][1] = b[i]

ab.sort()
L = []
n = 1
maxn = 1

for i in range(N-1):
    if i == 0:
        ColorV[0] = 0
        ColorV[1] = 1
        L.append(1)
    else:
        if ab[i][0] == ab[i-1][0]:
            if n + 1 != ColorV[ab[i][0]-1]:
                ColorV[ab[i][1]-1] = n+1
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
            else:
                ColorV[ab[i][1]-1] = n+2
                L.append(n+2)
                n = n+2
                if n >= maxn:
                    maxn = n
        else:
            n = 1
            if n != ColorV[ab[i][0]-1]:
                ColorV[ab[i][1]-1] = n
                L.append(n)
                if n >= maxn:
                    maxn = n
            else:
                ColorV[ab[i][1]-1] = n
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
print(maxn)
for i in range(N-1):
    print(L[i])

Submission status: Wrong Answer

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

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

graph = [[] for i in range(N)]
for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

color = [[] for i in range(N)]
L = []
K = 0
for e in edge:

    i = 0
    while True:
        if i not in color[e[0]-1] and i not in color[e[1]-1]:
            L.append(i)
            color[e[0]-1].append(i)
            color[e[1]-1].append(i)
            K = max(K,i+1)
            break
        i += 1

print(K)
for l in L:
    print(l+1)

Submission status: Wrong Answer

Solution code:
n = int(input())
keys =[]
leaves = {}
values = []
results = []
for i in range(n-1):
    e = input().split()
    if e[0] not in keys and e[1] not in keys:
        results.append("1")
        leaves.update({e[0] : 1})  
        keys.append(e[0])  
        leaves.update({e[1] : 1})    
        keys.append(e[1])
    elif e[0] not in keys and e[1] in keys:
        leaves.update({e[0] : 1}) 
        keys.append(e[0])
        results.append(int(leaves[e[1]])+1)
        leaves[e[1]] += 1
    elif e[0] in keys and e[1] not in keys:
        leaves.update({e[1] : 1}) 
        keys.append(e[1])
        results.append(int(leaves[e[0]])+1)
        leaves[e[0]] += 1
    else:
        if int(leaves[e[0]]) > int(leaves[e[1]]):
            results.append(int(leaves[e[0]])+1)
        else: 
            results.append(int(leaves[e[1]])+1)
        leaves[e[0]] += 1   
        leaves[e[1]] += 1

for key in leaves:
    values.append(leaves[key])

m = max(values)
print(m)

for r in results:
    print(r)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [[int(i) for i in input().split()] for _ in range(n-1)]
s = p[0][0]
e = p[0][1]
l = []
c = 0

for i in p:
    if s==i[0] or e ==i[0]:
        c+=1
        l.append(c)
    else:
        c=1
        l.append(c)
    s=i[0]
    e =i[1]

max = max(l)
print(max)
for i in l:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
ltmp=[0 for i in range(n)]
l=[list(map(int,input().split())) for _ in range(n-1)]
for i in l:
    ltmp[i[0]-1]+=1
    ltmp[i[1]-1]+=1
d=max(ltmp)
lans=[0 for i in range(n)]
print(d)
for i in l:
    lans[i[0]-1]+=1
    lans[i[1]-1]+=1
    print(max(lans[i[0]-1],lans[i[1]-1]))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab = [[int(i) for i in input().split()] for j in range(n-1)]

graph = [[] for i in range(n+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
ans = [float('inf')]*(n+1)
visit = [False] * (n+1)

abc = float('inf')
for aa in range(len(graph[1:])):
    if len(graph[aa])>=3:
        abc=aa
if abc ==float('inf'):
    abc = 1


que = [abc]

ans[abc]=1
while que:
    q = que.pop()
    visit[q] = True
    for i in graph[q]:
        if not visit[i]:
            visit[i] = True
            que.append(i)
            ans[i]=ans[q]+1
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=[[] for i in range(n)]
d=[]
for i in range(n-1):
  c[l[i][0]-1].append((l[i][1]-1,i))
  c[l[i][1]-1].append((l[i][0]-1,i))
for i in range(n):
  d.append(len(c[i]))
print(max(d))
color=[set() for i in range(n)]

if max(d)==n-1:
  for i in range(i):
    print(i+1)
  sys.exit()
for i in range(n-1):
  for j in range(1,n+1):
    if j not in color[l[i][0]-1] and j not in color[l[i][1]-1]:
      print(j)
      break
  color[l[i][0]-1].add(j)
  color[l[i][1]-1].add(j)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*(N-1)
b = [0]*(N-1)
for i in range(N-1):
    a[i], b[i] = map(int, input().split())
ColorV = [0]*(N)
ab = [[0,0] for _ in range(N-1)]
for i in range(N-1):
    ab[i][0] = a[i]
    ab[i][1] = b[i]

ab.sort()
print(ab)
L = []
n = 1
maxn = 1

for i in range(N-1):
    if i == 0:
        ColorV[0] = 0
        ColorV[1] = 1
        L.append(1)
    else:
        if ab[i][0] == ab[i-1][0]:
            if n + 1 != ColorV[ab[i][0]-1]:
                ColorV[ab[i][1]-1] = n+1
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
            else:
                ColorV[ab[i][1]-1] = n+2
                L.append(n+2)
                n = n+2
                if n >= maxn:
                    maxn = n
        else:
            n = 1
            if n != ColorV[ab[i][0]-1]:
                ColorV[ab[i][1]-1] = n
                L.append(n)
                if n >= maxn:
                    maxn = n
            else:
                ColorV[ab[i][1]-1] = n
                L.append(n+1)
                n = n+1
                if n >= maxn:
                    maxn = n
print(maxn)
for i in range(N-1):
    print(L[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
graf = [[] for _ in range(n)]
colorU = [-1 for _ in range(n)]
colorD = [-1 for _ in range(n)]
colorU[0] = 0

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

for i in range(n):
    # print(i)
    a = ab[i][0]
    b = ab[i][1]
    c = ab[i][2]

    a -= 1
    b -= 1
    # print(i)
    if colorD[a] == -1:
        if colorU[a] == 1:
            thiscolor = 2
        else:
            thiscolor = 1
    else:
        thiscolor = colorD[a] + 1
        if thiscolor == colorU[a]: #1本目以外
            thiscolor += 1

    colorU[b] = thiscolor
    colorD[a] = thiscolor
    ans[c] = thiscolor
    # print(i)
    # print(thiscolor, i)

print(max(ans))
for i in ans:
    print(i)

# i = 0
# j = 0
# lasta = 0
#
# for l in range(n):
#     a, b = map(int, input().split())
#     if a != lasta:
#         i = a - 1
#         j = 0
#
#     if j == 0:
#         thiscolor = color[i] + 1
#     else:
#         thiscolor = graf[a][j - 1] + 1
#
#     graf[i].append()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC146 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
edge = [[] for _ in range(n)]
lst = []
for _ in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    lst.append((a,b))

cnt = 0
for i in range(n):
    cnt = max(cnt,len(edge[i]))
#print(cnt)

ans = [None]*n

que = deque()
que.append((0,1,-1))
tmp = 1
ans[0] = 1
tmpv = 0
while que:
    v,color,p = que.popleft()
    if ans[v] == None:
        tmpv = v
        if tmp == color:
            if tmp == cnt:
                ans[v] = 1
                tmp = ans[v]
            else:
                ans[v] = color + 1
                tmp = ans[v]
        else:
            ans[v] = tmp
        tmp += 1
    if tmp > cnt:
        tmp = 1
    x = 1
    for u in edge[v]:
        if ans[u] == None:
            que.append((u,ans[v],v))
print(cnt)
for i in ans[:-1]:
    print(i)

Submission status: Wrong Answer

Solution code:
N=int(input());AB=[list(map(int,input().split())) for _ in range(1,N)]
nd=[0 for _ in range(N)]
table = [[] for _ in range(N)]
for a,b in AB:
  table[a-1].append(b)
  nd[a-1]+=1
  nd[b-1]+=1

for li in table:
  li.sort()

K=max(nd)
print(K)
co=[0 for _ in range(N)]
for x,li in enumerate(table):
  c=[i for i in range(1,K+1) if i != co[x]]
  for b,y in zip(li,c):
    co[b-1]=y
    print(y)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

adj_dict = {}

for edge in edge_list:
    if edge[0] not in adj_dict.keys():
        adj_dict[edge[0]] = [(edge[1])]
    else:
        adj_dict[edge[0]].append(edge[1])
    if edge[1] not in adj_dict.keys():
        adj_dict[edge[1]] = [(edge[0])]
    else:
        adj_dict[edge[1]].append(edge[0])

max_color = -1

# print(adj_dict)

for key in adj_dict:
    temp_num = 0
    # print('key')
    for item in adj_dict[key]:
        # print(item)
        temp_num += 1
    # print(temp_num)
    if temp_num > max_color:
        # print(temp_num, max_color)
        max_color = temp_num


print(max_color)

result = 1

incrementing = False

# print(len(edge_list))

for j in range(len(edge_list)):
    if j == 0:
        print(1)
        continue
    if edge_list[j][0] in edge_list[j-1] or edge_list[j][1] in edge_list[j-1]:
        result += 1
        print(result)
        incrementing = True
    else:
        if incrementing:
            incrementing = False
            result = 1
            print(result)
        else:
            print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque

N=int(input())
vcol=[set() for v in range(N+1)];vcol[0]=None

e=[None]
for i in range(1,N):
    a,b=map(int,input().split())
    if not vcol[a] and not vcol[b]:
        col=1
    else:
        col=1
        while col in vcol[a]|vcol[b]:
            col+=1
    vcol[a].add(col);vcol[b].add(col)
    e.append(col)

#print(vcol)
print(max(e[1:]))
for ei in e[1:]:
    print(ei)

Submission status: Wrong Answer

Solution code:

N = int(input())

T = [[] for i in range(N)]
F = [None for i in range(N-1)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    F[i] = b-1

# print(T)

R = [None for i in range(N)]
def dfs(cur, mx, color):
    R[cur] = color
    if color == -1:
        mx = max(len(T[cur]), mx)
    else:
        mx = max(len(T[cur])+1, mx)
    d = 0
    mmx = mx
    # for i,t in enumerate(T[cur], start=1):
    #     if i==color:
    #         d=1
    #     mmx = max(mmx,dfs(t, mx, i+d))
    #     # dfs(t, mx, i)
    return mmx
M = dfs(0, 1, -1)
# print(R)
# print(F)
print(M)
for i,f in enumerate(F):
    print(R[f])

Submission status: Wrong Answer

Solution code:


n = int(input())
tree = {}

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


color = len(tree[1])
for key in tree.keys():
  if key == 1:
    continue
    
  arr = tree[key]
  color = max(len(arr)+1, color)

print(color)

iro = [0] * (n+1)

for key in tree.keys():
  my_color = iro[key]
  arr = tree[key]
  for i in arr:
    my_color += 1
    iro[i] = my_color % color

for i in b_arr:
  print(iro[i]+1)