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())
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)
print(d)
lans=[set() for _ in range(d)]
for i in l:
    for j in range(d):
        if i[0] not in lans[j] and i[1] not in lans[j]:
            lans[j].add(i[0])
            lans[j].add(i[1])
            print(j+1)
            break

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

N = I()
AB = LRI(N - 1)

g = {i : 0 for i in range(1, N + 1)}

for a, b in AB:
    g[a] += 1
    g[b] += 1

ans = max(g.values())

print(ans)
for i in range(N - 1):
    print((i % ans) + 1)

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)
tmp = 1
while que:
    v = que.popleft()
    if ans[v] == None:
        ans[v] = tmp
        tmp += 1
    if tmp > cnt:
        tmp -= cnt
    for u in edge[v]:
        if ans[u] == None:
            que.append(u)
print(*ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
r=[]
d={}
s=[[]for _ in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  d[min(a,b)*1000000+max(a,b)]=0
  r.append((a,b))
  s[a-1].append(b-1)
  s[b-1].append(a-1)
Q=[(0,i)for i in s[0]]
co=[10**6]*n
while Q:
  P=[]
  j=0
  for i in range(len(Q)):
    a,b=Q[i]
    j+=1
    if j==co[a]:j+=1
    d[min(a+1,b+1)*1000000+max(a+1,b+1)]=j
    co[b]=j
    for ii in s[b]:
      if a!=ii:P.append((b,ii))
  Q=P
print(max(len(s[i])for i in range(n)))
for a,b in r:print(d[min(a,b)*1000000+max(a,b)])

Submission status: Wrong Answer

Solution code:
# ABC146d
ans = 1


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)

    # map(int,input().split())

    n = int(input())

    edges = [list() for _ in range(n)]
    colors = [-1] * (n - 1)

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

    def dfs(i, color, pre):
        nc = 0 if color != 0 else 1
        for e in edges[i]:
            if e[0] == pre:
                continue
            global ans
            if ans < len(edges[i]):
                ans = len(edges[i])
            colors[e[1]] = nc
            dfs(e[0], nc, i)
            nc += 1
    dfs(0, -1, -1)
    print(ans)
    for i in colors:
        print(i+1)


if __name__ == '__main__':
    main()

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 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:
N = int(input())
tree = [[] for _ in range(N)]
ans = [0]*(N-1)
for i in range(N-1):
    a,b = map(int,input().split())
    ans[i] = (max(len(tree[a-1]), len(tree[b-1])))
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
ma = 0
for t in tree:
    ma = max(ma,len(t))
print(ma)
for i in range(N-1):
    print(ans[i]+1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
t = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    t[a - 1].append(b - 1)
    t[b - 1].append(a - 1)
    e.append([a - 1, b - 1])

colors = [len(t[i]) for i in range(n)]
res1 = max(colors)
print(res1)

flag = [[] for _ in range(n)]
res = []
for a, b in e:
    for i in range(1, res1 + 1):
        if not i in flag[a] and not i in flag[b]:
            print(i)
            flag[a].append(i)
            flag[b].append(i)
            break

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

# txt = "100000"
# for i in range(99999):
#     txt += "\n" + str(i) +" " +  str(i+1)
# def i():
#     for l in txt.split("\n"):
#         yield l
# input = i().__next__
def main():
    N = int(input())
    mawari = [[] for _ in range(N)]
    e_num = [0] * N 
    for l in range(N-1):
        i, j = [int(x)-1 for x in input().split()]
        e_num[i] += 1
        e_num[j] += 1
        mawari[i].append((j, l))
        mawari[j].append((i, l))
    look = -1
    for ind, l in enumerate(e_num):
        if l == 1:
            look = ind
            break
    color = [-1]*(N-1)
    c_prev = deque([-1])
    to_visit = deque([look])
    maxc = 0
    while len(to_visit)>=1:
        look = to_visit.pop()
        c = 0
        prevc = c_prev[-1]
        for i,j in mawari[look]:
            if color[j] != -1:
                continue
            if c == prevc:
                c += 1
            color[j] = c
            c_prev.append(c)
            to_visit.append(i)
            maxc = max(maxc, c)
            c += 1
        
    # mc, c = a(N, 0, look, color, mawari, -1)
    print(maxc+1)
    for i in color:
        print(i+1)


# def a(N, maxc, look, color, mawari, prev):
#     nexts = mawari[look]
#     c = 0
#     for i,j in nexts:
#         if c == prev:
#             c += 1
#         color[j] = c
#         maxc = max(maxc, a(N, maxc, i, color, mawari, c)[0])
#         c += 1
#     return maxc, color
    

main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

marker = [[0] for i in range(N)]
edge_color = [0] * (N - 1)

for i in range(N - 1):
    color = 1
    while(True):
        if color not in marker[a[i] - 1] and color not in marker[b[i] - 1]:
            edge_color[i] = color
            marker[a[i] - 1].append(color)
            marker[b[i] - 1].append(color)
            break
        else:
            color += 1

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

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    g=[[] for _ in [0]*n]
    [g[a-1].append(b-1) for a,b in ab]
    [g[b-1].append(a-1) for a,b in ab]
    color=[-1]*n
    color[0]=0
    q=[[0,0]]
    while q:
        qq=[]
        while q:
            i,root=q.pop()
            cnt=1
            for j in g[i]:
                if j==root:
                    continue
                if cnt==color[i]:
                    cnt+=1
                color[j]=cnt
                cnt+=1
                qq.append([j,i])
        q=qq
    print(max(color[1:]))
    for i in color[1:]:
        print(i)
main()

Submission status: Wrong Answer

Solution code:
N=int(input())
info=[list(map(int, input().split())) for _ in range(N-1)]
lst=[[] for i in range(N+1)]
for (a, b) in info:
  lst[a].append(b)
  lst[b].append(a)
K=max(len(l) for l in lst)
color_map=[[False for _ in range(K+1)] for _ in range(N+1)]
color_list=[0 for i in range(N-1)]
for i in range(N-1):
  a, b=info[i]
  for j in range(1, K+1):
    if not color_map[a][j] and not color_map[b][j]:
      color_map[a][j]=True
      color_map[b][j]=True
      color_list[i]=j
      break
print(K)
for i in range(N-1):
  print(color_list[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)
print(d)
lans=[[] for _ in range(d)]
for i in l:
    for j in range(d):
        if i[0] not in lans[j] and i[1] not in lans[j]:
            lans[j].append(i[0])
            lans[j].append(i[1])
            print(j+1)
            break

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return "".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def nibu(a,b,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2
        if ll == mid:
            return ll
        co = mid * a
        mm = mid
        while mm != 0:
            co += b
            mm //= 10 
        if co >= r:
            rr = mid-1
        else:
            ll = mid


n = onem()

kkk = [[] for i in range(n)]

for i in range(n-1):
    a,b = m()
    kkk[a-1].append(b-1)
    kkk[b-1].append(a-1)
de = cl.deque([[0,0,0]])
kk= []
while de:
    j,k,p = de.popleft()
    kk.append(p)
    co = 1
    for i in range(len(kkk[j])):
        if not kkk[j][i] == k:
            if co == p:
                co += 1
            de.append([kkk[j][i],j,co])
            co += 1
print(max(kk))

for i in range(n-1):
    print(kk[1+i])

Submission status: Wrong Answer

Solution code:
import collections
def main():

    N = int(input())
    edge = [[] for _ in range(N)]
    ncol = 0
    start = None
    graph = collections.defaultdict(list)
    pair = collections.defaultdict(dict)
    for i in range(N-1):
        a, b = map(int, input().split())
        edge[a-1].append(i)
        edge[b-1].append(i)
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        pair[a-1][b-1] = i
        pair[b-1][a-1] = i
        if len(graph[a-1]) > ncol:
            ncol = len(graph[a-1])
            start = a-1
        if len(graph[b-1]) > ncol:
            ncol = len(graph[b-1])
            start = b-1

    n = max(edge)
    cols = [0 for _ in range(N-1)]
    idx = 1
    for i in edge[start]:
        cols[i] = idx
        idx += 1
    visited = set([start])
    m = idx-1
    cur = [[h, cols[pair[start][h]]] for h in graph[start]]

    while cur:
        temp = []
        for node, c in cur:
            idx = 0
            for h in graph[node]:
                if cols[pair[node][h]] == 0:
                    if idx == c:
                        idx += 1
                    cols[pair[node][h]] = idx
                    idx += 1
                    temp.append([h, cols[pair[node][h]]])
        cur = temp
    print(m)
    for i in range(N-1):
        print(cols[i])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100005)

N=int(input())
edges = [0 for i in range(N)]
edge_l = [[] for i in range(N)]
cols = [0 for i in range(N)]
out = 0
seen = [False for i in range(N)]
seen2 = [False for i in range(N)]

def paint(cur, parC):
  if seen[cur]:
    return
  curC = 1
  seen[cur] = True
  for e in edge_l[cur]:
    if not seen2[e[1]]:
      seen2[e[1]] = True
      if curC == parC:
        curC+=1
      cols[e[1]] = curC
      paint(e[0], cols[cur])
      curC+=1
  return

for i in range(N-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges[a]+=1
  edges[b]+=1
  edge_l[a].append([b,i])
  edge_l[b].append([a,i])
  out = max(out,edges[a],edges[b])
print(out)
paint(0,0)
for i in range(N-1):
  print(cols[i])

Submission status: Wrong Answer

Solution code:
import collections
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A, B = I[1::2], I[2::2]
s = collections.defaultdict(set)
for i, ab in enumerate(zip(A, B)):
    a, b = ab
    s[a].add(i)
    s[b].add(i)
c = collections.Counter(A + B)
d = c.most_common()[::-1]
K = d[-1][1]
ans = [None] * (N - 1)
used = [set() for _ in range(N + 1)]
while d:
    p, _ = d.pop()
    L = 1
    for i in s[p]:
        if ans[i] is None:
            while L in used[A[i]] or L in used[B[i]]:
                L += 1
            ans[i] = L
        used[A[i]].add(ans[i])
        used[B[i]].add(ans[i])
print(K)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
count = [0]*N
side = []
node = [[]for i in range(N)]
ans = [0]*N
for i in range(N-1):
    a,b = map(int,input().split())
    count[a-1] += 1
    count[b-1] += 1
    side.append([b-1])
    node[a-1].append(i)

K = max(count)
def DFS(x,m):
    for i in range(min(len(node[x])),m-1):
        ans[node[i]] = i+1
        DFS(side[node[i]],i+1)
    for i in range(m,min(len(node[x]))):
        ans[node[i]] = i+1
        DFS(side[node[i]],i+1)

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        ab = [tuple(map(int, input().split())) for _ in range(N - 1)]

        nodes = defaultdict(int)

        K = 0
        for a, b in ab:
            nodes[a] += 1
            nodes[b] += 1
            K = max([K, nodes[a], nodes[b]])

        print(K)
        color = defaultdict(list)
        for a, b in ab:
            for k in range(1, K + 1):
                if k not in color[a] and k not in color[b]:
                    print(k)
                    color[a].append(k)
                    color[b].append(k)
                    break


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

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

N = int(input())

A = [0]*N
L = [[]for i in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    for j in range(1, N+1):
        if j in L[a-1]:
            continue
        else:
            L[a-1].append(j)
            L[b-1].append(j)
            A[i] = j
            break

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

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
    for k, v in tmdd.items():
        if v > m_in:
            m_in = v
            m_no = k

    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, 10 ** 5):
                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:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  query = [[] for _ in range(n)]
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    a -= 1
    b -= 1
    query[a].append((b,i))
    query[b].append((a,i))
  ans = 0
  for i in range(n):
    ans = max(ans,len(query[i]))
  print(ans)
  node = deque([])
  stack = [[] for _ in range(n)]
  for i in range(n):
    if len(query[i]) == ans:
      node.append((i,ans))
      break
  for i in range(n):
    stack[i] = (len(query[i]))
  #print(stack)
  tmp = [-1]*(n-1)
  visit = [False]*n
  while node:
    #print(node)
    place,maxnode = node.popleft()
    for j,i in query[place]:
        tmp[i] = max(tmp[i],maxnode)
        maxnode -= 1
        
        if visit[j]:
          continue
        else:
          node.append((j,stack[j]))
    visit[place] = True
    
    
  for i in tmp:
    print(i)
solve()

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
	N = int(input())
	vertex_color_list = [set() for _ in range(N + 1)]
	# print(vertex_color_list)
	edge_color_list = []
	for _ in range(N - 1):
		a, b = map(int, input().split())
		for i in range(1, 10**5):
			if (i not in vertex_color_list[a]) and (i not in vertex_color_list[b]):
				vertex_color_list[a].add(i)
				vertex_color_list[b].add(i)
				edge_color_list.append(i)
				break
	K = max(edge_color_list)
	print(K)
	for s in edge_color_list:
		print(s)

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] = 1
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            cur = 1
            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
                    cur += 1
                    if G_ans[v] == G_ans[u]:
                        G_ans[v] = (G_ans[u] + cur) % deg_max
                        cur += 1
                    Q.append(v)
            G_color[u] = 'BLACK'
    bfs(G[0][0])
    print(deg_max)
    for g in G_ans[1:]:
        print(g+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
ans = []
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			ans.append(kk)
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

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

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
es = [[] for _ in range(n + 1)]
counter = [0 for _ in range(n + 1)]
for _ in range(n - 1):
	a, b = list(map(int, input().split()))
	es[a].append(b)
	counter[a] += 1
	counter[b] += 1

#print(counter)
max_e = collections.Counter(counter).most_common()[0][1]
colors = [0 for _ in range(n + 1)]


for i in range(1, n + 1):
	#print(colors)
	c = colors[i]
	#print(es[i])
	for j in range(1, len(es[i]) + 1):
		colors[es[i][j - 1]] = (c + j) % max_e

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

Submission status: Wrong Answer

Solution code:
N = int(input())
E = sorted([list(map(int, input().split())) for _ in range(N-1)], key = lambda x:x[1])
E.sort()
ans = []
flg = [0 for _ in range(N+1)]

t = 0
cnt = 0
ans_a = 0
for i in range(N-1):
	a,b = E[i]
	if t != a:
		cnt = 1
		t = a
	if flg[a] == cnt:
		cnt += 1
	ans.append(cnt)
	flg[b] = cnt
	ans_a = max(ans_a, cnt)
	cnt += 1
	

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

Submission status: Wrong Answer

Solution code:
N = int(input())
E ={i:[] for i in range(N+1)}
ab = []
for i in range(N-1):
  a,b = [int(x)  for x in input().split()]
  ab.append((a,b,i))
  E[a].append((b,i))
  E[b].append((a,i))
visited=[0]*(N+1)
stk = [[1,-1,0]]
ans = [0]*(N-1)
while stk:
  v,p,r = stk.pop()
  if visited[v]:
    continue
  visited[v]=1
  if r!=1:
    r=0
  for i,j in E[v]:
    if i!=p:
      stk.append([i,v,r+1])
      r=r+1
      ans[j]=r
print(max(ans))
for i in range(N-1):
	print(ans[i])

Submission status: Wrong Answer

Solution code:
def examD():
    N = I()
    cur = [0]*(N-1)
    super = [0]*(N+1)
    d = defaultdict(int)
    for i in range(N-1):
        a, b = LI()
        d[a] +=1
        if d[a]!=super[a]:
            cur[i] = d[a]
        else:
            d[a] +=1
            cur[i] = d[a]
        super[b] = cur[i]
    ans = max(cur)
    print(ans)
    for i,v in enumerate(cur):
        print(v)


def examE():
    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

input = sys.stdin.readline

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

downnum = [0]*N
neighbor = [[] for i in range(N)]
for ai, bi in ab:
	downnum[ai-1] += 1
	neighbor[ai-1].append(bi-1)

K = max(max(downnum[1::])+1, downnum[0])
Kpre = [-1]*N
Kpre[0] = K
ans = []
queue = [0]
knum = 1
while len(queue)>0:
	nq = []
	for i in queue:
		kk = Kpre[i]+1
		if kk>K: kk -= K
		for j in neighbor[i]:
			ans.append(kk)
			nq.append(j)
			Kpre[j] = kk
			kk += 1
			if kk>K: kk -= K

	queue = nq

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

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append(list(map(int,input().split())))
for i in range(N-1):
    AB[i][0] = AB[i][0]-1
    AB[i][1] = AB[i][1]-1
Edges =[[] for _ in range(N)]
for i in range(N-1):
    Edges[AB[i][0]].append(AB[i][1])
    Edges[AB[i][1]].append(AB[i][0])
c = 0
for i in range(N):
    if c < len(Edges[i]):
        c = len(Edges[i])
usedColors = [[] for _ in range(N)]
print(c)
for i in range(N-1):
    a,b = AB[i][0],AB[i][1]
    if len(usedColors[a]) == 0 and len(usedColors[b]) == 0:
        print(1)
        usedColors[a].append(1)
        usedColors[b].append(1)
    else:
        for k in range(1,c+1):
            if k not in usedColors[a] and k not in usedColors[b]:
                print(k)
                usedColors[a].append(k)
                usedColors[b].append(k)
                break

Submission status: Wrong Answer

Solution code:
def main():
    n = input()
    tree = {}
    edge = []
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        if a not in tree:
            tree[a] = {}
        if b not in tree:
            tree[b] = {}
        tree[a][b] = None
        tree[b][a] = None
        edge.append([a, b])
    colors = max(len(b) for b in tree.itervalues())
    print colors
    stack = [1]
    while stack:
        node = stack.pop()
        nei = tree[node]
        unused = iter(set(range(1, colors + 1)) - {c for c in nei.itervalues() if c is not None})
        for nex in nei.keys():
            col = nei[nex]
            if col is not None:
                continue
            nei[nex] = next(unused)
            stack.append(nex)
    for a, b in edge:
        print tree[a][b]


main()

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 a, b in edges:
    cur = 1
    while cur in used[a] or cur in used[b]:
        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())
L=[]
for i in range(n-1):
  l=list(map(int,input().split()))
  L.append(l)

k=1
ans=[]
ans.append(1)
for i in range(n-1):
  if i==0:
    pass
  else:
    if L[i][0]==L[i-1][0] or L[i][0]==L[i-1][1]:
      k+=1
      ans.append(k)
    else:
      k=1
      ans.append(k)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import Counter
from itertools import chain
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Solver(object):
    def __init__(self):
        pass

    def solve(self, n: int, links: list):
        # flatten the links
        flatten_links = list(chain.from_iterable(links))
        max_count = Counter(flatten_links).most_common()[0][1]
        print(max_count)
        n_colors = [set() for _ in range(n)]
        ans = list()
        for link in links:
            if len(link) == 2:
                for c in range(1, max_count+1):
                    if c not in n_colors[link[0]-1] and c not in n_colors[link[1]-1]:
                        ans.append(c)
                        n_colors[link[0] - 1].add(c)
                        n_colors[link[1] - 1].add(c)
                        break
        for i in ans:
            print(i)


def main():
    N = int(input())
    t_l = [[int(i) for i in input().split()] for _ in range(N)]

    solver = Solver()
    solver.solve(N, t_l)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
def input() -> str:
    return sys.stdin.readline().rstrip()
n = int(input())
edges = [input().split() for _ in range(n - 1)]
colors = defaultdict(list)
answer = []
for a, b in edges:
  c = 1
  while True:
    if c not in colors[a] and c not in colors[b]:
      colors[a].append(c)
      colors[b].append(c)
      answer.append(c)
      break
    c += 1
print(max(answer), *answer, sep="\n")

Submission status: Wrong Answer

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

chk = [set() for _ in range(N)]
cnt = 1
ans = [0] * (N-1)

for i in range(N-1):
    color = 1
    while True:
        if color not in chk[G[i][0]-1] and color not in chk[G[i][1]-1]:
            break
        else:
            color += 1
    chk[G[i][0]-1].add(color)
    chk[G[i][1]-1].add(color)
    ans[i] = color
    cnt = max(cnt, color)

print(cnt)
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
E=[]
CT=[0]*n
for i in range(n-1):
  a,b=map(int,input().split())
  E.append((a,b))
  CT[a-1]+=1
  CT[b-1]+=1
ans=max(CT)
print(ans)
Ans=[]
E.sort(key=lambda x:(x[0],x[1]))
Chk=[0]*n
for a,b in E:
  if Chk[a-1]==0:
    print(1)
    Chk[a-1]+=1
    Chk[b-1]+=1
  else:
    print(Chk[a-1]+1)
    Chk[a-1]+=1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)
        
    s = [(1, -1)]
    done = set([1])
    K = 0
    ans = {}
    while s:
        u, c = s.pop()
        used = set([c])
        c = 1
        for v in g[u]:
            if v in done:
                continue
            while c in used:
                c += 1 
                K = max(K, c)
            used.add(c)
            s.append((v, c))
            i, j = min(u, v), max(u, v)
            ans[(i, j)] = c
            done.add(v)
    print(K)
    for a, b in AB:
        print(ans[(a, b)])
    # return ans


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
t=[]
for i in range(n-1):
    t.append(list(map(int,input().split())))
ans=[0]*(n-1)
sa=[0]*(n)
for i in range(n-1):
    x=t[i][0]-1
    y=t[i][1]-1
    ans[i]=max(sa[x],sa[y])+1
    sa[x]+=1
    sa[y]+=1
print(max(ans))
for i in ans:
    print(i)