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())
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])!=1:
        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:
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
rl = [0] * (N - 1)

abd = {}
for a, b in ab:
  abd[a] = abd.get(a,{})
  abd[a][b] = 0
  abd[a]["c"] = abd[a].get("c", set())
  abd[a]["c"].add(len(abd[a]["c"]) + 1)
  abd[b] = abd.get(b,{})
  abd[b][a] = 0
  abd[b]["c"] = abd[b].get("c", set())
  abd[b]["c"].add(len(abd[b]["c"]) + 1)
rk = max([len(x) for x in abd.values()])
print(rk - 1)

for a, b in ab:
  c = abd[a]["c"].pop()
  abd[b]["c"].discard(c)
  print(c)

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:
def main():
    N = int(input())
    lines = [list(map(int, input().split())) for i in range(N-1)]

    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:
def f(x):
  return int(x) - 1

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

v = [[-1] for _ in range(N)]
col = []
K = 0
for a, b in ab:
    for k in range(1,K+1):
        if (not k in v[a]) and (not k in v[b]):
            v[a].append(k)
            v[b].append(k)
            col.append(k)
            break
    else:
        K += 1
        v[a].append(K)
        v[b].append(K)
        col.append(K)
        
print(K)
for c in col:
    print(c)

Submission status: Wrong Answer

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

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

for i in range(N-1):
    a, b = map(int, input().split())
    cur = 1
    #s = used[a] | used[b]
    while cur in used[a]:
        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:
from collections import defaultdict
import random

class Graph():
    def __init__(self):
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight
    
    def edge_num(self, node):
        return len(self.edges[node])
    
    def set_weight(self, from_node, to_node, weight):
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight
    
    def has_node_weight(self,node):
        node_set = set()
        for x in self.edges[node]:
            node_set.add(self.weights[(node,x)])
        return node_set

    def done(self):
        if min(self.weights) > 0:
            return True
        else:
            return False

N = int(input())
A = [0]*N
B = [0]*N

g = Graph()

for i in range(N-1):
    A[i], B[i]  = map(int,input().split())
    A[i], B[i] = A[i]-1, B[i]-1
    g.add_edge(A[i], B[i],0)

lines = [0]*N
for n in range(N):
    lines[n] = g.edge_num(n)

K = max(lines)
K_node = lines.index(K)

n = 1
for node in g.edges[K_node]:
    g.set_weight(K_node, node, n) 
    n += 1

for node in g.edges[K_node]:
    m = 1
    for x in g.edges[node]:
        if x == K_node:
            continue
        if m == g.weights[(node, K_node)]:
            m += 1
        g.set_weight(node, x, m) 
        m += 1

for n in range(N):
    for node in g.edges[n]:
        if g.weights[(n, node)] != 0:
            continue
        else:
            weight = random.choice(list(set(range(1,K+1))-g.has_node_weight(node)))
            g.set_weight(n,node,weight)

def output():
    print(K)
    for i in range(N-1):
        print(g.weights[(A[i], B[i])])
    
output()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
all_color = set()
for i in range(n-1):
    x,y = map(int,input().split())
    a.append(x)
    b.append(y)
    all_color.add(i+1)

ex = []
for i in range(n):
    ex.append(set())

color = [0]*(n-1)
count = [0]*n
for i in range(n-1):
    count[a[i]-1] += 1
    count[b[i]-1] += 1
    cand = (all_color - (ex[a[i]-1] | ex[b[i]-1])).pop()
    ex[a[i]-1].add(cand)
    ex[b[i]-1].add(cand)
    color[i] = cand
print(max(count))
for c in color:
    print(c)

Submission status: Wrong Answer

Solution code:
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)]

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())
v = [tuple(map(int, input().split())) for _ in range(n-1)]

tmp = {x: [] for x in range(1, n+1)}
ans = []
for a, b in v:
    c = 1
    while True:
        if c not in tmp[a] and c not in tmp[b]:
            ans.append(c)
            tmp[a].append(c)
            tmp[b].append(c)
            break
        else:
            c += 1

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

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:
        if len(C[e[0]]) == 0 and len(C[e[1]]) > 0:
            t = 1
            while t in C[e[1]]:
                t += 1
            print(t)
            C[e[1]].add(t)
            C[e[0]].add(t)
        elif len(C[e[0]]) > 0 and len(C[e[1]]) == 0:
            t = 1
            while t in C[e[0]]:
                t += 1
            print(t)
            C[e[0]].add(t)
            C[e[1]].add(t)
        else:
            print(1)
            C[e[1]].add(1)
            C[e[0]].add(1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
used_col={i:set() for i in range(n)}
col_list=[]
for i in range(n-1):
    a,b = map(int,input().split())
    # a=i+1
    # b=i+2
    a-=1
    b-=1
    a_used_col = used_col[a]
    b_used_col = used_col[b]
    for i in range(n):
        if i+1 not in a_used_col and i+1 not in b_used_col:
            c = i+1
            break
    col_list.append(c)
    used_col[a].add(c)
    used_col[b].add(c)
print(max(col_list))
for x in col_list:
    print(x)

Submission status: Wrong Answer

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

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

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

for a, b in ab:
    graph[a-1].append((b-1, -1))
    # graph[b-1].append((a-1, -1))

# print(graph)

stack = [(0, -1)]
visited = [-1]*n

k = 0
while stack:
    node, color = stack.pop()

    if k < len(graph[node])+1:
        k = len(graph[node])+1
    tmp = 1
    for i, (child, child_color) in enumerate(graph[node]):

        if child_color == -1:
            if tmp == color:
                tmp += 1
            graph[node][i] = (child, tmp)
            stack.append((child, tmp))
            tmp +=1

print(k)
for a, b in ab:
    print(list(filter(lambda x: x[0]==(b-1), graph[a-1]))[0][1])

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
node = [
    tuple(map(int, input().split())) for i in range(n-1)
]

color = np.zeros(n+1)
for i in range(n-1):
    color[node[i][0]] += 1
    color[node[i][1]] += 1

counter = np.copy(color)
print(int(max(color)))

for i in range(n-1):
    if color[node[i][0]] > color[node[i][1]]:
        pr = node[i][0]
    else:
        pr = node[i][1]
    print(int(counter[pr]))
    counter[node[i][0]] -= 1
    counter[node[i][1]] -= 1

Submission status: Wrong Answer

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

N = int(input())
edge = [[] for i in range(N)]
count = [0] * N
color = {}
egs = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    count[a] += 1
    count[b] += 1
    edge[a].append(b)
    edge[b].append(a)
    egs.append(tuple(sorted([a, b])))


ans = max(count)
c = 1



def dfs(idx, pr):
    c = 1
    col = color[pr]
    for i in edge[idx]:
        if i not in pr:
            if c == col:
                c+=1
            x, y = sorted([i, idx])
            color[(x, y)] = c
            dfs(i, (x, y))
        c+=1

color[(-1, -1)] = 0
dfs(0, (-1, -1))
print(ans)
for tpl in egs:
    print(color[tpl])

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
a = []
b = []
for i in range(N-1):
    a.append(ab[i][0])
for i in range(N-1):
    b.append(ab[i][1])
    
ab_max = []
for i in range(N-1):
    ab_max.append(a[i])
    ab_max.append(b[i])
c = collections.Counter(ab_max)    
    
ans = max(c.values())

print(ans)

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

ndic = {}
for i in range(1, N+1):
    ndic[i] = []

for i in range(N-1):
    a_and_b = set(l) ^ (set(ndic[a[i]]) ^ set(ndic[b[i]]))
    p = min(a_and_b)
    print(p)
    ndic[a[i]].append(p)
    ndic[b[i]].append(p)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

edge = 0
only = []

for i in range(1, N+1):
  if a.count(i) + b.count(i) == 1:
    edge += 1
    only.append(i)

color = 1

print(edge)

for i in range(0, N-1):
  print(color)
  if a[i] in only or b[i] in only:
    color += 1

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 = []
n -= 1
for i in range(n):
    # print(i)
    a, b = map(int, input().split())
    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.append(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:
import sys
input=sys.stdin.readline
n=int(input())
edges=list(list(map(int,input().split())) for _ in range(n-1))
data=list([] for _ in range(n)) #各辺を端点に持つ辺
for i in range(n-1):
  data[edges[i][0]-1].append(i)
  data[edges[i][1]-1].append(i)
colors=max(map(len,data))
print(colors)
result=[0 for _ in range(n-1)] #各辺の色
for i in range(n-1):
  if list(result[j] for j in data[edges[i][0]-1]).count(1)>=1 or list(result[j] for j in data[edges[i][1]-1]).count(1)>=1:
    for k in range(i):
      result[k] = result[k]%colors+1
  result[i]=1
for r in result:
  print(r)

print(result)

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    ab = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n-1)]
    tmd = collections.defaultdict(list)
    tmdd = collections.defaultdict(int)
    m_in = 0
    m_no = -1
    for a, b in ab:
        tmd[a] += [b]
        tmd[b] += [a]
        tmdd[a] += 1
        tmdd[b] += 1
    cnt = 0
    for k, v in tmdd.items():
        if v > m_in:
            m_in = v
            m_no = k
        elif v == m_in:
            cnt += 1
    m_in = m_in if cnt != len(tmd) - 1 and len(tmd) == 3 else m_in + 1

    ql = [[0, m_no]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[m_no]
    aq = collections.defaultdict(int)
    while True:
        if len(ql) != 0:
            cost, tmp = ql.popleft()
            ls = []
            limit = tmdd[tmp]
            for i in range(1, m_in + 1):
                if i != cost:
                    ls.append(i)
                if len(ls) >= limit:
                    break
            for tmv in tmd[tmp]:
                if tmv not in fq:
                    p = ls.pop()
                    ql.append([p, tmv])
                    fq[tmv]
                    aq[tmp, tmv] = p
                    aq[tmv, tmp] = p
        else:
            break
    print(m_in)
    for a, b in ab:
        print(aq[a, b])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]
    G_ans = [0 for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        G_ans[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            cur = 1
            cur_set = set()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    G_ans[v] = (G_ans[u] + cur) % deg_max
                    while G_ans[v] in cur_set:
                        G_ans[v] = (G_ans[u] + cur) % deg_max
                        cur += 1
                    cur += 1
                    cur_set.add(G_ans[v])
                    Q.append(v)
            G_color[u] = 'BLACK'
    bfs(G[0][0])
    print(deg_max)
    for g in G_ans[:N-1]:
        print(g+1)


if __name__ == '__main__':
    main()

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
while que:
    v,color,p = que.popleft()
    if ans[v] == None:
        if tmp == color:
            if tmp == cnt:
                ans[v] = 1
                tmp = ans[v]
            else:
                if p == 0:
                    ans[v] = color
                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:
    print(i)

Submission status: Wrong Answer

Solution code:

from collections import deque
n = int(raw_input())
edges = []
for i in range(n-1):
    edges.append(map(int, raw_input().split()))

edge_to_i = {}
graph = [[] for _ in range(n+1)]
ans = [0] * (n-1)

for i in range(len(edges)):
    s,e = edges[i]
    graph[s].append(e)
    graph[e].append(s)
    edge_to_i[(s, e)] = i
    edge_to_i[(e, s)] = i

visited = set([])
q = deque([1])
while q:
    node = q.popleft()
    visited.add(node)
    color = 1

    not_colored = []
    colors = set([])
    for next_node in graph[node]:
        i = edge_to_i[(next_node, node)]
        if ans[i] == 0:
            not_colored.append(i)
        else:
            colors.add(ans[i])
        if not next_node in visited:
            q.append(next_node)

    color = 1
    for i in not_colored:
        while color in colors:
            color += 1
        ans[i] = color
        color += 1

print len(ans)
for i in ans:
    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

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

Submission status: Wrong Answer

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

n=int(input())

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

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

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





listtmp = [[0 for i in range(n+1)] for j in range(n+1)]
k=0
for i in range(n-1):
	for j in range(1,n):
		tmp=(k+j)%maxapexcount+1
		if(listtmp[ai[i]][tmp]!=1)and(listtmp[bi[i]][tmp]!=1):
			listtmp[ai[i]][tmp]=1
			listtmp[bi[i]][tmp]=1
			print(tmp)
			k=tmp
			break

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:
        if len(C[e[0]]) and len(C[e[1]]) > 0:
            t = 1
            while t in C[e[1]]:
                t += 1
            print(t)
            C[e[1]].add(t)
            C[e[0]].add(t)
        elif len(C[e[0]]) > 0 and len(C[e[1]]) == 0:
            t = 1
            while t in C[e[0]]:
                t += 1
            print(t)
            C[e[0]].add(t)
            C[e[1]].add(t)
        else:
            print(1)
            C[e[1]].add(1)
            C[e[0]].add(1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from collections import Counter

def flatten_2dim(array):
    return [item for sublist in array for item in sublist]


n = int(input())

arr = []
idx = 0
num = 0
max = 0
for i in range(n - 1):
    arr.append([])
    arr[i] = [int(x) for x in input().split()]
    if num == 0:
        num = arr[i][0]
    if num == arr[i][0]:
        idx += 1
    else:
        num = arr[i][0]
        idx = 1
    for j in range(len(arr) - 1):
        if arr[i][0] == arr[j][1] and idx == arr[j][2]:
            idx += 1
    arr[i].append(idx)
    if max < idx:
        max = idx

arr = sorted(sorted(arr, key=itemgetter(1)), key=itemgetter(0))

print(max)
for i in range(len(arr)):
    print(arr[i][2])

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def main():
#    h,w,a,b = map(int, input().split())
    n=int(input())
    b = [[] for i in range(n)]
    c = [[0 for j in range(n)] for i in range(n)]
    d=[]
    for i in range(n-1):
        x,y=map(int,input().split())
        b[x-1].append(y)
        b[y-1].append(x)
        d.append([x,y])
#    print(b)
#    print(d)
    for i in range(n):
        temp=[]
        for j in b[i]:
            if c[i][j-1]==0:
                for l in range(1,10**5):
                    if l in temp:
                        continue
                    else:
                        c[i][j-1]=l
                        c[j-1][i]=l
                        temp.append(l)
                        break
            else:
                temp.append(c[i][j-1])
 #   print(c)
    e=[]
    for i in range(n):
        e.append(max(c[i]))
    print(max(e))
    for i in range(n-1):
        print(c[d[i][0]-1][d[i][1]-1])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
color = [0]*(n-1)
color[0] = 1
max_ans = 0
for i in range(1,n-1):
    if ab[i][0] == ab[i-1][0]:
        color[i] += color[i-1] +1
    elif ab[i][0] == ab[i-1][1]:
        color[i] = 2
    else:
        color[i] = 1
    if max_ans < color[i]:
        max_ans = color[i]
print(max_ans)
for j in range(n-1):
    print(color[j])

Submission status: Wrong Answer

Solution code:
K = int(input())
nodes = [(int(s) for s in input().split()) for _ in range(K - 1)]

nodes_num = [0 for _ in range(K)]
for a, b in nodes:
  nodes_num[a - 1] += 1
  nodes_num[b - 1] += 1

max_value = -1
max_index = -1
for i, nn in enumerate(nodes_num):
  if nn > max_value:
    max_index = i
print(max_index)

Submission status: Wrong Answer

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

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

for i in range(N-1):
    a, b = map(int, input().split())
    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:
n=int(input())
AB=[]
Tree=[[] for _ in range(n)]
c=[0]*n
ans=[[0]*n for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    AB.append([a,b])
    Tree[a-1].append(b)
    Tree[b-1].append(a)
    c[a-1]+=1
    c[b-1]+=1
k=max(c)
p=c.index(k)+1
x=0
for l in Tree[p-1]:
    x+=1
    ans[p-1][l-1]=x
    ans[l-1][p-1]=x
def dsf(p,v):
    used=ans[p-1][v-1]
    x=0
    for l in Tree[v-1]:
        x+=1
        if x==used:
            x+=1
        if l!=p:
            ans[v-1][l-1]=x
            ans[l-1][v-1]=x
            dsf(v,l)
for l in Tree[p-1]:
    dsf(p,l)
for ab in AB:
    print(ans[ab[0]-1][ab[1]-1])

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)]
edge.sort()

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[0]-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:
from collections import defaultdict
N = int(input())


AB = []

D = defaultdict(list)


for n in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D[a].append(b)
    D[b].append(a)
    AB.append((a, b, n))

AB.sort()

ans = 0
for i in range(N):
    l = len(D[i])
    if ans < l:
        ans = l

print(ans)

E = defaultdict(int)

res = []

for a, b, n in AB:
    E[a] += 1
    E[b] += 1
    res.append((n, E[a]))

res.sort()
for _, r in res:
    print(r)

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] and c not in 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())
graph = [[] for i in range(N)]
basho = {}
for i in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    graph[a].append(b)
    graph[b].append(a)
    s = str(a) + '-' + str(b)
    basho[s] = i
#print(basho)
#print(graph)
maxi = 0
for i in range(N):
    leni = len(graph[i])
    maxi = max(leni, maxi)
K = maxi
color = [0 for i in range(N-1)]
for i in range(N):
    v = graph[i]
    colk = [False for nnn in range(K)]
    for j in v:
        if i < j:
            n = str(i) + '-' + str(j)
        else:
            n = str(j) + '-' + str(i)
        #print(n)
        if color[basho[n]] == 0:
            ind = colk.index(False)
            color[basho[n]] = ind + 1
            colk[ind] = True
        else:
            colk[color[basho[n]]-1] = True
print(K)
for i in range(N-1):
    print(color[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
colors = [[] for _ in range(n + 1)]
leaf = []
max = 0
for _ in range(n - 1):
    a, b = map(int, input().split())
    for j in range(1, 100001):
        if j not in colors[a] and j not in colors[b]:
            leaf.append(j)
            colors[a].append(j)
            colors[b].append(j)
            if max < j:
                max = j
            break

print(max)
for l in leaf:
    print(l)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    colors = {}
    all_edges = {}
    edges = {}
    order = []
 
    for i in range(1,n+1):
        edges[i] = []
        colors[i] = set()
        
    for i in range(n-1):
        a,b = map(int,input().split())
        edges[a].append(b)
        edges[b].append(a)
        all_edges[(a,b)] = 0
        order.append((a,b))
 
    k = 0
    for i in edges.keys():
        k = max(k,len(edges[i]))

    color = 1
    visited = set()
    for i in range(1,n):
        if i not in visited:
            visited.add(i)
            for kid in edges[i]:
                if kid not in visited:
                    all_edges[(i,kid)] = color
                    color += 1
 
    print(k)
    for i in order:
        if all_edges[i] > k:
            all_edges[i] -= k
        print(all_edges[i])
 
main()