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:
import sys
from collections import deque
input = sys.stdin.readline

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

def main():
    N = int(input())
    node = list(range(1,N+1))
    edges = {i:set() for i in node}
    edge_lines = list(readlines(N-1))
    for u, v in edge_lines:
        edges[u].add(v)
        edges[v].add(u)
    
    colors = tuple(range(1, N+1))
    ans = {edge:0 for edge in edge_lines}
    ans[edge_lines[0]] = 1
    succ = deque()
    succ.append((0,edge_lines[0][0]))
    colored = set()
    while succ:
        if 0 not in ans.values():
            break
        p, u = succ.popleft()
        colored_around = set()
        if p > 0:
            colored_around.add(ans[p, u])
        for v in edges[u]:
            u1, v1 = u, v
            if (u,v) not in edge_lines:
                u1, v1 = v, u

            if (u1, v1) in colored:
                continue

            succ.append((u1,v1))
            colored.add((u1, v1))
            color = [color for color in colors if color not in colored_around][0]
            ans[u1, v1] = color
            colored_around.add(color)
    maxi = max(ans.values())
    print(maxi)
    for c in ans.values():
        print(c)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

count = [0] * (n+1)
path = defaultdict(lambda: [])
for a, b in ab:
    path[a].append(b)
    path[b].append(a)
    count[a] += 1; count[b] += 1

size = max(count)
# print(size)

d = deque()
d.append(1)

is_checked = [0] * (n+1)
colors = [0] * (n+1)
color = 0
is_checked[1] = 1
while len(d) > 0:
    num = d.pop()
    color += 1

    for next_num in path[num]:
        if not is_checked[next_num]:
            d.append(next_num)
            is_checked[next_num] = 1
    colors[num] = (color % size) + 1


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

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
S = [tuple(map(int, input().split())) for i in range(N-1)]
S.sort()
l=[0]*N
t=1
k=0
A=[]
for i in S:
    if t==i[0]:
        k+=1
        if k==l[i[0]-1]:
            k+=1
        A.append(k)
        l[i[1]-1]=k
    else:
        t=i[0]
        k=1
        if 1==l[i[0]-1]:
            k=2
        A.append(k)
        l[i[1]-1]=k
print(max(A))
print(*A,sep="\n")

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7

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

colors = {1}
ans = []
edges = [set() for _ in range(N)]
for ab in ab_n:
    set_a = edges[ab[0] - 1]
    set_b = edges[ab[1] - 1]
    colors_ab = set_a | set_b
    next_colors = colors - colors_ab

    c = len(colors) + 1 if len(next_colors) == 0 else list(next_colors)[0]

    colors |= {c}
    set_a |= {c}
    set_b |= {c}

    ans.append(str(c))

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
edge = [set() for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].add((b, i))
    edge[b].add((a, i))
    
r = [0] * (N-1)
q = deque([(0, 1)])

while q:
    print(edge)
    preC, fromv = q.popleft()
    c = 0
    for tov, i in edge[fromv]:
        edge[tov].remove((fromv, i))
        c += 1 + (c + 1 == preC)
        q.append((c, tov))
        r[i] = c

print(max(r))
for x in r:
    print(x)

Submission status: Wrong Answer

Solution code:


N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]
colors = [set() for i in range(N+1)]

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

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()

    next = 1
    for v in edges[u]:
      if v != p and v not in visited:
        c = colors[u] | colors[v]
        
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        colors[u].add(next)
        colors[v].add(next)
        visited.add(v)
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

Submission status: Wrong Answer

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
import copy 
w = copy.deepcopy(W)
d = {}
w.sort()
k = 0
for i in range(N-1):
    a,b = w[i]
    x = k + 1
    d[a+b*N] = x
    k += 1
    k = k % K
for i in range(N-1):
    a,b = W[i]
    print(d[a+b*N])

Submission status: Wrong Answer

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


n = int(input())

GRAPH = {i:[] for i in range(1, n + 1)}
COLORS = {(0, 1):0}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)
    COLORS[(a, b)] = 0

PREV = {1:0}
Q = [1]
while Q:
    now = Q.pop(0)
    for vertex in GRAPH[now]:
        if vertex == PREV[now]:
            continue
        next = vertex
        PREV[next] = now
        Q.append(next)

Q = [1]
while Q:
    now = Q.pop(0)
    prev = PREV[now]
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    
    color = 1
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        next = vertex
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
        Q.append(next)

print(max(COLORS.values()))

EDGES = sorted(COLORS.keys())[1:]
for edge in EDGES:
    print(COLORS[edge])

Submission status: Wrong Answer

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


n = int(input())

GRAPH = {i:[] for i in range(1, n + 1)}
COLORS = {(0, 1):0}
for _ in range(n - 1):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)
    COLORS[(a, b)] = 0

PREV = {1:0}
Q = [1]
while Q:
    now = Q.pop(0)
    for vertex in GRAPH[now]:
        if vertex == PREV[now]:
            continue
        next = vertex
        PREV[next] = now
        Q.append(next)

Q = [1]
while Q:
    now = Q.pop(0)
    prev = PREV[now]
    a, b = min(now, prev), max(now, prev)
    used = COLORS[(a, b)]
    
    color = 1
    for vertex in GRAPH[now]:
        if vertex == prev:
            continue
        next = vertex
        a, b = min(now, next), max(now, next)
        if color == used:
            color += 1
            COLORS[(a, b)] = color
            color += 1
        else:
            COLORS[(a, b)] = color
            color += 1
        Q.append(next)

print(max(COLORS.values()))
for color in list(COLORS.values())[1:]:
    print(color)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]*N
X = [[] for j in range(N+1)]
Y = [0]*(N-1)
Z = [[0 for i in range(2)] for j in range(N-1)]
#Z=[[0,0]]*(N-1)
#print(Z)
for i in range(N-1):
    x,y=input().split()
    x=int(x)
    y=int(y)
    Z[i][0]=x
    Z[i][1]=y
    A[x-1]+=1
    A[y-1]+=1
    #print(Z)
    #X[]
A.sort()
max=A[N-1]
#print(Z)
for i in range(N-1):
    x=Z[i][0]
    y=Z[i][1]
    for j in range(1,max+1):
        if(j not in X[x] and j not in X[x]):
            Y[i]=j
    X[x].append(j)
    X[y].append(j)
    #print(X)
print(max)
for i in range(N-1):
    #print("\n")
    print(Y[i])

#print(A)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [0]*N
X = [[] for j in range(N+1)]
Y = [0]*(N-1)
Z = [[0 for i in range(2)] for j in range(N-1)]
#Z=[[0,0]]*(N-1)
#print(Z)
for i in range(N-1):
    x,y=input().split()
    x=int(x)
    y=int(y)
    Z[i][0]=x
    Z[i][1]=y
    A[x-1]+=1
    A[y-1]+=1
    print(Z)
    #X[]
A.sort()
max=A[N-1]
#print(Z)
for i in range(N-1):
    x=Z[i][0]
    y=Z[i][1]
    for j in range(1,max+1):
        if(j not in X[x] and j not in X[x]):
            Y[i]=j
    X[x].append(j)
    X[y].append(j)
    #print(X)
print(max)
for i in range(N-1):
    #print("\n")
    print(Y[i])

#print(A)

Submission status: Wrong Answer

Solution code:
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    tree[a].append(b)
    tree[b].append(a)

# print(tree)

# visitedにノードの色を格納する
visited = [0] * N

# bfsによる色付けを行う
def bfs(s):
    queue = [[tree[s], 1]]
    while queue:
        next_nodes, before_color = queue.pop(0)
        now = 1
        for next_node in next_nodes:
            if visited[next_node] == 0:
                if now != before_color:
                    visited[next_node] = now
                else:
                    now += 1
                    visited[next_node] = now
                # print("next_node : ",next_node)
                # print("before_color : ",before_color)
                queue.append([tree[next_node], now])
                now += 1

for i in range(N - 1):
    if len(tree[i]) == 1:
        start = i
        break
visited[start] = 1
bfs(start)
for val in visited:
    print(val)

Submission status: Wrong Answer

Solution code:
from collections import*
from copy import*
import sys
sys.setrecursionlimit(10**8)

n=int(input())
if n<9999:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=deque(range(1,m+1))
        for i in d[point]:
            if tuple(sorted([point,i])) not in dcolars:
                ckamo=colar.pop()
                if c==ckamo:
                    csave=deepcopy(ckamo)
                    ckamo=colar.pop()
                    colar.append(csave)
                dcolars[tuple(sorted([point,i]))]=ckamo
                BFS(d,i,ckamo)
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

else:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=0
        for i in d[point]:
            colar+=1
            if tuple(sorted([point,i])) not in dcolars:
                if c==colar:
                    colar+=1
                dcolars[tuple(sorted([point,i]))]=colar
                dcolars[tuple(sorted([point,i])[::-1])]=colar
                BFS(d,i,colar)
    
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import*
from copy import*
import sys
sys.setrecursionlimit(10**8)

n=int(input())
if n<9000:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=deque(range(1,m+1))
        for i in d[point]:
            if tuple(sorted([point,i])) not in dcolars:
                ckamo=colar.pop()
                if c==ckamo:
                    csave=deepcopy(ckamo)
                    ckamo=colar.pop()
                    colar.append(csave)
                dcolars[tuple(sorted([point,i]))]=ckamo
                BFS(d,i,ckamo)
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

else:
    d=defaultdict(list)
    
    q=[]
    for i in range(n-1):
        a,b=map(int,input().split())
        d[a].append(b)
        d[b].append(a)
        q.append(tuple(sorted([a,b])))
        
    #print(d)
    m=max(map(len,d.values()))
    print(m)
    
    dcolars={}
    
    def BFS(d,point,c):
        colar=0
        for i in d[point]:
            colar+=1
            if tuple(sorted([point,i])) not in dcolars:
                if c==colar:
                    colar+=1
                dcolars[tuple(sorted([point,i]))]=colar
                dcolars[tuple(sorted([point,i])[::-1])]=colar
                BFS(d,i,colar)
    
        return dcolars
    
    ans=BFS(d,1,0)
    
    for i in q:
        print(ans[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [list(map(int, input().split())) for _ in [0] * (n-1)]

a = [0] * n

for i in s:
    a[i[0]-1] += 1
    a[i[1]-1] += 1

print(max(a))

b = [0] * n

for i in s:
    b[i[0]-1] += 1
    b[i[1]-1] += 1
    print(max(b[i[0]-1], b[i[1]-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque


N = int(input())
B = []
L = []
for i in range(N-1):
    ta,tb = map(int,input().split())
    B.append(ta)
    B.append(tb)
    L.append([ta,tb])
B =B[1::2]
E = [[] for _ in range(N + 1)]
for a, b in L:
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for i in range(N-1):
    print(C[i+2])

Submission status: Wrong Answer

Solution code:

from collections import deque

N = int(input())

E = [[] for _ in range(N + 1)]
for i in range(N-1):
    ta,tb = map(int,input().split())
    E[ta-1].append(tb-1)

Q = deque([0])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for i in range(1,N):
    print(C[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

ki = [[] for i in range(N)]
kita = [False] * N

iros = [None] * (N - 1)

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

iros[0] = 1

irokazu = 0

q = deque()
q.append((0, -1))

while len(q) > 0:
    node, oyanoiro = q.popleft()
    kita[node] = True
    tsugis = ki[node]

    kouho = set(range(1, len(tsugis) + 1))
    tsukatta = {oyanoiro}
    for tsugi, henbangou in tsugis:
        print(kouho, tsukatta)
        if kita[tsugi]:
            continue

        tsuginoiro = min(kouho - tsukatta)
        tsukatta.add(tsuginoiro)
        iros[henbangou] = tsuginoiro
        irokazu = max(irokazu, tsuginoiro)

        q.append((tsugi, iros[henbangou]))

print(irokazu)
for iro in iros:
    print(iro)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())

tree = [[0]*n for _ in range(n)]
color_node = [[0]*n for _ in range(n)]

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

colors = 0
root = 0
for i in range(n):
    if sum(tree[i]) > colors:
        colors = sum(tree[i])
        root = i

que = deque([])
visited = [False] * n

col = 1
for i in range(n):
    if tree[root][i] == 1:
        color_node[root][i] = col
        color_node[i][root] = col
        col += 1
        que.append((i,root))
visited[root] = True

while que:
    node, parent = que.pop()
    if visited[node] == True:
        continue
    visited[node] = True
    for i in range(n):
        if tree[node][i]==1 and color_node[node][i]==0:
            new_col = color_node[parent][node] + 1
            if new_col==col:
                new_col = 1
                
            color_node[node][i] = new_col
            color_node[i][node] = new_col
            que.append((i,node))

print(col-1)
for i in range(n-1):
    x,y = lst[i]
    print(color_node[x-1][y-1])

Submission status: Wrong Answer

Solution code:

N = int(input())
edges = [input().split() for i in range(N-1)]

v = [[] for i in range(N+1)]

ans = []

for i in range(N-1):
  a, b = map(int, edges[i])
  
  # 頂点の色を見つける
  next = 1
  for j in sorted(v[a] + v[b]):
    if j != next:
      break
    next += 1
  
  v[a].append(next)
  v[b].append(next)
  ans.append(next)

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

Submission status: Wrong Answer

Solution code:

N = int(input())
edges = [input().split() for i in range(N-1)]

v = [[] for i in range(N+1)]

ans = []

for i in range(N-1):
  a, b = map(int, edges[i])
  
  # 頂点の色を見つける
  next = 1
  for j in sorted(v[a] + v[b]):
    if j == next:
      next += 1
  
  v[a].append(next)
  v[b].append(next)
  ans.append(next)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())

tree = [[0]*n for _ in range(n)]
color_node = [[0]*n for _ in range(n)]

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

colors = 0
root = 0
for i in range(n):
    if sum(tree[i]) > colors:
        colors = sum(tree[i])
        root = i

que = deque([])
visited = [False]*n

#親に隣接する辺を最初に色分け
col = 1
for i in range(n):
    if tree[root][i] == 1:
        color_node[root][i] = col
        color_node[i][root] = col
        col += 1
        que.append((i,0))
visited[root] = True

while que:
    node, parent = que.pop()
    
    for i in range(n):
        if tree[node][i]==1 and color_node[node][i]==0:
            new_col = color_node[parent][node] + 1
            if new_col==col:
                new_col = 1
            color_node[node][i] = new_col
            color_node[i][node] = new_col
            que.append((i,node))

print(col-1)
for i in range(n-1):
    x,y = lst[i]
    print(color_node[x-1][y-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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


graph = defaultdict(set)
for v1, v2 in edges:
    graph[v1].add(v2)
    graph[v2].add(v1)


dq = deque([])
dq.append(edges[0][0])

visit = set()

used_color_dic = defaultdict(set)
colors = [[0] * (N + 1) for _ in range(N + 1)]


while dq:
    fr = dq.popleft()
    can_set = graph[fr]

    for to in can_set:
        if fr <= to:
            t = (fr, to)
        else:
            t = (to, fr)

        if t in visit:
            continue

        used_set = used_color_dic[fr]

        for i in range(1, N + 1):
            if i not in used_set:
                used_color_dic[fr].add(i)
                used_color_dic[to].add(i)

                colors[fr][to] = i
                colors[to][fr] = i
                break

        dq.append(to)
        visit.add((fr, to))


max_ = 0
for k, v in used_color_dic.items():
    max_ = max(max_, len(v))

print(max_)

# output
for v1, v2 in edges:
    print(colors[v1][v2])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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


graph = defaultdict(set)
for v1, v2 in edges:
    graph[v1].add(v2)
    graph[v2].add(v1)


dq = deque([])
dq.append(edges[0][0])

visit = set()

used_color_dic = defaultdict(set)
colors = [[0] * (N + 1) for _ in range(N + 1)]


while dq:
    fr = dq.popleft()
    can_set = graph[fr]

    for to in can_set:
        if fr <= to:
            t = (fr, to)
        else:
            t = (to, fr)

        if t in visit:
            continue

        used_set = used_color_dic[fr]

        for i in range(1, N):
            if i not in used_set:
                used_color_dic[fr].add(i)
                used_color_dic[to].add(i)

                colors[fr][to] = i
                colors[to][fr] = i
                break

        dq.append(to)
        visit.add((fr, to))


max_ = 0
for k, v in used_color_dic.items():
    max_ = max(max_, len(v))

print(max_)

# output
for v1, v2 in edges:
    print(colors[v1][v2])

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
E = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  E[a-1].append(b-1)

C = [[] for _ in range(N)]
ans = []

for idx,edge in enumerate(E):
  c = 1
  for e in edge:
    if c in C[idx]:
      c += 1
    C[e].append(c)
    ans.append(c)
    c += 1
print(max(ans))
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
E = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  E[a-1].append(b-1)

C = [deque(range(1,N)) for _ in range(N)]
ans = []

for idx,edge in enumerate(E):
  for e in edge:
    c = C[idx].popleft()
    C[e].remove(c)
    ans.append(c)
print(max(ans))
for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

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

dic = {}
color = {}
root = [0]*N

for i in range(N):
    dic[i+1] = []
for n in range(N-1):
    i = ab[n][0]
    j = ab[n][1]
    dic[i].append(j)
    dic[j].append(i)
    root[i-1] += 1
    root[j-1] += 1
    color[(i,j)] = 0
root_node = root.index(1)+1
def rec(now_node,prevcolor):
    nowcolor = 0
    tg_list = dic[now_node][:]
    for elem in tg_list:
        nowcolor += 1
        if nowcolor == prevcolor:
            nowcolor += 1
        dic[elem].remove(now_node)
        color[(elem,now_node)] = nowcolor
        color[(now_node,elem)] = nowcolor
        rec(elem,nowcolor)
rec(root_node,0)
for n in range(N-1):
    i = ab[n][0]
    j = ab[n][1]
    print(color[(i,j)])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())

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

used_color_dic = defaultdict(set)
edge_color = []

for v1, v2 in edges:
    used_set1 = used_color_dic[v1]
    used_set2 = used_color_dic[v2]
    for i in range(1, N):
        if i not in used_set1 and i not in used_set2:
            used_color_dic[v1].add(i)
            used_color_dic[v2].add(i)
            break

    edge_color.append(i)

num_color = 0
for i in range(1, N + 1):
    num_color = max(len(used_color_dic[i]), num_color)

# output
print(num_color)
for x in edge_color:
    print(x)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())

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

used_color_dic = defaultdict(set)
edge_color = []

for v1, v2 in edges:
    used_set = used_color_dic[v1]
    for i in range(1, N):
        if i not in used_set:
            used_color_dic[v1].add(i)
            used_color_dic[v2].add(i)
            break

    edge_color.append(i)

num_color = 0
for i in range(1, N + 1):
    num_color = max(len(used_color_dic[i]), num_color)

print(num_color)
for x in edge_color:
    print(x)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())

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

used_color_dic = defaultdict(set)
edge_color = []

for v1, v2 in edges:
    used_set = used_color_dic[v1]
    for i in range(N):
        if i not in used_set:
            used_color_dic[v1].add(i)
            used_color_dic[v2].add(i)
            break

    edge_color.append(i)

num_color = 0

for i in range(1, N + 1):
    num_color = max(len(used_color_dic[i]), num_color)

print(num_color)
for x in edge_color:
    print(x + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())

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

for i in range(n - 1):
    f, t = map(int, input().split())
    graph[f - 1].append(t - 1)
    graph[t - 1].append(f - 1)

que = deque([(0, None)])
visited = [False] * n
visited[0] = True
edge = [None] * n

while que:
    now, skip = que.popleft()
    i = 0
    for t in graph[now]:
        if not visited[t]:
            if i == skip:
                i += 1
            que.append((t, i))
            visited[t] = True
            edge[t] = i + 1
            i += 1


edge = edge[1:]
print(max(edge))
list(map(print, edge))

Submission status: Wrong Answer

Solution code:
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            l = min(now,ne); r = max(now,ne)
            if W[D[(l,r)]] == -1:
                low = 0; upper = n-1
                while(upper-low>1):
                    i = (low+upper)//2
                    if used[(now,i)]:
                        low = i
                    else:
                        upper = i
                used[(now, upper)] = True
                used[(ne, upper)] = True
                que.append(ne)
                W[D[(l,r)]] = upper
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,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 LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
def bfs(n,e,fordfs,D):
    #点の数、スタートの点、有向グラフ
    W = [-1]*(n-1)
    #各点の状態量、最短距離とか,見たかどうかとか
    used = defaultdict(bool)
    que = deque()
    que.append(e)
    while que:
        now = que.popleft()
        for ne in fordfs[now]:
            if W[D[(now,ne)]] == -1:
                i = 1
                while(True):
                    if not used[(now,i)]:
                        used[(now, i)] = True
                        used[(ne, i)] = True
                        break
                    i +=1
                que.append(ne)
                if now<ne:
                    W[D[(now,ne)]] = i
                else:
                    W[D[(ne, now)]] = i
    return W
def examD():
    N = I()
    V = [[]for _ in range(N)]
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        d[(a-1,b-1)] = i
    ans = bfs(N,0,V,d)
    print(max(ans))
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,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 LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
import queue

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

max_k = 0

q = queue.Queue()
q.put(0)
while not q.empty():
    k = 0
    now = q.get()
    c_list = node_color[now]
    n_list = nodes[now]
    remove_c = 0
    for c in c_list:
        if c != 0:
            remove_c = c
            break
            
    for node in n_list:
        k+=1
        if k == remove_c:
            k+=1
        node_color[now][node] = k
        node_color[node][now] = k
        q.put(node)
    if max_k < k:
        max_k = k

print(max_k)

for i in range(n):
    for j in range(i+1, n):
        if node_color[i][j] != 0:
            print(node_color[i][j])

Submission status: Wrong Answer

Solution code:
n = int(input())
node_col = [set() for _ in range(n)]
maxc = 0
anslist = []
for i in range(n-1):
    a,b = map(int,input().split())
    for i in range(1,n+1):
        if (not i in node_col[a-1]) and (not i in node_col[b-1]):
            node_col[a-1].add(i)
            node_col[b-1].add(i)
            anslist.append(i)
            maxc = max(maxc,i)
            break
print(maxc)
for p in anslist:print(p)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
mp=[[] for i in range(N+1)]

for i in range(N-1):
    a,b=LI()
    mp[a].append((b, i))
    mp[b].append((a, i))

ma = 0
ma_e = 0
for i, arr in enumerate(mp):
    if len(arr) > ma:
        ma = len(arr)
        ma_e = i

CLS = [0]*(N-1)
VISITED = [0]*(N+1)
Q=deque([(ma_e, 0)])
VISITED[ma_e] = 1

while Q:
    v, c = Q.popleft()
    cnt = 1
    for next_e, i in mp[v]:
        if VISITED[next_e]: continue
        color = ((c + cnt) % ma) + 1
        CLS[i] = color

        Q.append((next_e, color))
        VISITED[next_e] = 1
        cnt += 1

print(ma)
for i in CLS: print(i)