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())
R=[[] for i in range(N)]
C=[[] for i in range(N)]
a=[]
b=[]
L=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    R[a[i]].append(b[i])
    L.append(len(R[a[i]]))

K=max(L)

if len(set(a))!=1:K+=1
print(K)

for i in range(N-1):
    for k in range(1,K+1):
        if not k in C[a[i]]:
            print(k)
            C[a[i]].append(k)
            C[b[i]].append(k)
            break
        else:continue

Submission status: Wrong Answer

Solution code:
N=int(input())
R=[[] for i in range(N)]
C=[[] for i in range(N)]
a=[]
b=[]
L=[]

for i in range(N-1):
    ai,bi=map(int,input().split())
    a.append(ai-1)
    b.append(bi-1)
    R[a[i]].append(b[i])
    L.append(len(R[a[i]]))

K=max(L)

if len(R[0])!=K:
    K+=1
print(K)

for i in range(N-1):
    for k in range(1,K+1):
        if not k in C[a[i]]:
            print(k)
            C[a[i]].append(k)
            C[b[i]].append(k)
            break
        else:continue

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n+1)]
color = [set([]) for _ in range(n+1)]
ans = []
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    cnt = 1
    for i in tree[now]:
        if i in visited:
            pass
        else:
            q.append(i)
            # non-used color decided
            if cnt in color[now]:
                cnt += 1
            color[i].add(cnt)
            ans.append(cnt)
            cnt += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n+1)]
color = [set([]) for _ in range(n+1)]
ans = []
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)


q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    cnt = 1
    for i in tree[now]:
        if i in visited:
            pass
        else:
            q.append(i)
            if cnt in color[now]:
                cnt += 1
            color[i].add(cnt)
            ans.append(cnt)
            cnt += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n+1)]
color = [[] for _ in range(n+1)]
ans = []
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)


def color_check(x, a):
    if x in a:
        return color_check(x + 1, a)
    else:
        return x


q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    for i in tree[now]:
        if i in visited:
            pass
        else:
            q.append(i)
            cnt = color_check(1, color[now])
            color[now].append(cnt)
            color[i].append(cnt)
            ans.append(cnt)


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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
tree = [[] for _ in range(n+1)]
color = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)


def color_check(x, a):
    if x in a:
        return color_check(x + 1, a)
    else:
        return x


q = deque([1])
visited = {1}
while len(q) > 0:
    now = q.popleft()
    visited.add(now)
    cnt = 1
    for i in tree[now]:
        if i in visited:
            pass
        else:
            q.append(i)
            cnt = color_check(cnt, color[now])
            color[i].append(cnt)
            cnt += 1

print(*max(color))
for i in color[2:]:
    for j in i:
        print(j)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)

n = int(input())
arr = []

for i in range(n-1):
    S = input()
    ar = [int(s) for s in S.split(" ")]
    arr.append(ar)

def prepare(n, arr):
    data = [[] for i in range(n)]
    nodeStates = [-1 for i in range(n)]
    childNums = [0 for i in range(n)]

    for ar in arr:
        start = ar[0] - 1
        to = ar[1] - 1
        data[start].append(to)
        data[to].append(start)
    return data, nodeStates, childNums


data, nodeStates, childNums = prepare(n, arr)
mmk = {}
def generateID(start,to):
    if start < to:
        start,to = to, start

    return start * 10000 + to

def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    nodeStates[currentNode] = 1
    childNums[currentNode] = len(childNodes)
    kk = 0
    for ch in childNodes:
        if nodeStates[ch] == -1:
            kk = kk + 1
            if kk == x:
                kk = kk + 1
            mmk[generateID(currentNode+1,ch+1)] = kk
            dfs(ch, arr, kk)

dfs(0, data, -1)
print(max(childNums))
for ar in arr:
    start = ar[0]
    to = ar[1]
    print(mmk[generateID(start,to)])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict, deque

def dfs(tree, k):
  visited = []
  dq = deque()
  s = 1
  c = 0
  dq.append((-1, s, c))
  print(k)
  while dq:
    _, s, c = dq.popleft()
    visited.append(s)
    if _ != -1:
      print(c)
    count = 0
    for t in tree[s]:
      if t not in visited:
        dq.append((s, t, ((c+count) % (k)+1)))
        count += 1

def main():
  n = int(input())
  edges = [tuple(map(int, input().strip().split())) for _ in range(n-1)]
  counts = numpy.zeros(n)
  tree = defaultdict(list)
  for s, t in edges:
    counts[s-1] += 1
    counts[t-1] += 1
    tree[s].append(t)
    tree[t].append(s)
  k = int(numpy.max(counts))
  dfs(tree, k)

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:

N = int(input())
EDGES = []
P = [(set(), 1) for _ in range(N+1)]

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

_max = 0
ans = []
for (u, v) in EDGES:
  uset, umin = P[u]
  vset, vmin = P[v]
  index = max(umin, vmin)
  while index in uset and index in vset:
    index += 1
  else:
    umin = umin + 1 if umin == index else umin
    uset.add(index)
    P[u] = (uset, umin)
    vmin = vmin + 1 if vmin == index else vmin
    vset.add(index)
    P[v] = (vset, vmin)
  
  _max = max(_max, index)
  ans.append(index)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
raw = []
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw.append([a,b])
  peer[a].append(b)
  peer[b].append(a)
rank = [10**6 for _ in range(n)]
clr = [10**6 for _ in range(n)]
seen = [0 for _ in range(n)]
rank[0] = 0
clr[0] = 0
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        clr[y] = clr[x] + 1
        clr[x] += 1
        rank[y] = rank[x] + 1
        now.append(y)
maxi = 0
for i in range(n):
  maxi = max(maxi,len(peer[i]))
print(maxi)
for i in range(n-1):
  a,b = raw[i]
  if rank[a] < rank[b]:
    c = b
  else:
    c = a
  print(clr[c] % maxi + 1)
#print(clr)

Submission status: Wrong Answer

Solution code:
n = int(input())
raw = []
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw.append([a,b])
  peer[a].append(b)
  peer[b].append(a)
rank = [10**6 for _ in range(n)]
clr = [10**6 for _ in range(n)]
seen = [0 for _ in range(n)]
rank[0] = 0
clr[0] = 0
seen[0] = 0
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        clr[y] = clr[x] + 1
        clr[x] += 1
        rank[y] = rank[x] + 1
        now.append(y)
maxi = 0
for i in range(n):
  maxi = max(maxi,len(peer[i]))
print(maxi)
for i in range(n-1):
  a,b = raw[i]
  if rank[a] < rank[b]:
    c = b
  else:
    c = a
  print(clr[c] % maxi + 1)

Submission status: Wrong Answer

Solution code:
#13:33
n = int(input())
raw = []
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  raw.append([a,b])
  peer[a].append(b)
  peer[b].append(a)
rank = [10**6 for _ in range(n)]
clr = [10**6 for _ in range(n)]
seen = [0 for _ in range(n)]
rank[0] = 0
clr[0] = 0
seen[0] = 0
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        clr[y] = clr[x] + 1
        clr[x] += 1
        rank[y] = rank[x] + 1
        now.append(y)
maxi = 0
for i in range(n):
  maxi = max(maxi,len(peer[i]))
for i in range(n-1):
  a,b = raw[i]
  if rank[a] < rank[b]:
    c = b
  else:
    c = a
  print(clr[c] % maxi + 1)
#print(maxi)

Submission status: Wrong Answer

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [set() for _ in range(N+1)]
d = [0]*(N+1)
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append([a,b])
    tree[a].add(b)
    tree[b].add(a)
    d[a] += 1
    d[b] += 1

root = d.index(max(d))
l = len(tree[root])
print(l)
q = queue.Queue()
for i in range(1, l+1):
    y = tree[root].pop()
    if root < y:
        color[edges.index([root, y])] = i
    else:
        color[edges.index([y, root])] = i
    tree[y].remove(root)
    q.put([y, root, i])

Submission status: Wrong Answer

Solution code:
import queue

N = int(input())
edges = []
color = [0]*(N-1)
tree = [set() for _ in range(N+1)]
d = [0]*(N+1)
for i in range(N-1):
    a,b = map(int, input().split())
    edges.append([a,b])
    tree[a].add(b)
    tree[b].add(a)
    d[a] += 1
    d[b] += 1

root = d.index(max(d))
l = len(tree[root])
print(l)
q = queue.Queue()
for i in range(1, l+1):
    y = tree[root].pop()
    if root < y:
        color[edges.index([root, y])] = i
    else:
        color[edges.index([y, root])] = i
    tree[y].remove(root)
    q.put([y, root, i])

for _ in range(N-1):
    child, parent, e = q.get()
    l = len(tree[child])
    if l < e:
        colors = range(1, l+1)
    else:
        colors = [x for x in range(1, l+2) if x != e]
    for c in colors:
        y = tree[child].pop()
        if child < y:
            color[edges.index(sorted([child, y]))] = c
        else:
            color[edges.index(sorted([y, child]))] = c
        tree[y].remove(child)
        q.put([y, child, c])

Submission status: Wrong Answer

Solution code:
n = int(input())

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


ans = [0]*(n-1)

def col(now,color):
    c = 1
    for [b,j] in graph[now-1]:
        if c == color:
            c += 1
        ans[j-1] = c
        col(b,c)
        c += 1  

print(max(ans))
for i in range(1,n):
    print(ans[i-1])

Submission status: Wrong Answer

Solution code:
n = int(input()) - 1
_from = []
_to = []
_color = []
max_b = 0
for i in range(n):
    a,b = map(int,input().split())
    _from.append(a-1)
    _to.append(b-1)
    _color.append(0)
    max_b =  max(b, max_b)

v = [[] for _ in range(max_b)]
for i in range(n):
    j = 0
    while True:
        if ((j in v[_from[i]]) or (j in v[_to[i]])) == False:
            v[_from[i]].append(j)
            v[_to[i]].append(j)
            _color[i] = j + 1
            break
        j += 1
cnt = []
for i in range(max_b):
    cnt.append(len(v[i]))

print (max(cnt))
for i in range(n):
    print (_color[i])

Submission status: Wrong Answer

Solution code:
n = int(input()) - 1
_from = []
_to = []
_color = []
max_b = 0
for i in range(n):
    a,b = map(int,input().split())
    _from.append(a-1)
    _to.append(b-1)
    _color.append(0)
    max_b =  max(b, max_b)

v = [set() for _ in range(max_b)]
for i in range(n):
    j = 0
    while True:
        if ((j in v[_from[i]]) or (j in v[_to[i]])) == False:
            v[_from[i]].add(j)
            v[_to[i]].add(j)
            _color[i] = j + 1
            break
        j += 1
cnt = []
for i in range(max_b):
    cnt.append(len(v[i]))

print (max(cnt))
for i in range(n):
    print (_color[i])

Submission status: Wrong Answer

Solution code:
n = int(input()) - 1
_from = []
_to = []
_color = []
max_b = 0
for i in range(n):
    a,b = map(int,input().split())
    _from.append(a-1)
    _to.append(b-1)
    _color.append(0)
    max_b =  max(b, max_b)

v = [set() for _ in range(max_b)]
for i in range(n):
    j = 0
    while True:
        s = v[_from[i]] | v[_to[i]]
        if (j in s) == False:
            v[_from[i]].add(j)
            v[_to[i]].add(j)
            _color[i] = j + 1
            break
        j += 1
cnt = []
for i in range(max_b):
    cnt.append(len(v[i]))

print (max(cnt))
for i in range(n):
    print (_color[i])

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self,_from,_to):
        self._from = _from
        self._to = _to
        self._color = 0

n = int(input()) - 1
e_all = []
_from = []
_to = []
_color = []
max_b = 0
for i in range(n):
    a,b = map(int,input().split())
    _from.append(a-1)
    _to.append(b-1)
    _color.append(0)
    max_b =  max(b, max_b)

v = [[] for _ in range(max_b)]
for i in range(n):
    j = 0
    while True:
        while len(v[_from[i]]) <= j + 1:
            v[_from[i]].append(False)
        if v[_from[i]][j] == False:
            while len(v[_to[i]]) <= j + 1:
                v[_to[i]].append(False)
            if v[_to[i]][j] == False:
                v[_from[i]][j] = True
                v[_to[i]][j] = True
                _color[i] = j + 1
                break
        j += 1
cnt = []
for i in range(max_b):
    cnt.append(v[i].count(True))

print (max(cnt))
for i in range(n):
    print (_color[i])

Submission status: Wrong Answer

Solution code:
class edge:
    def __init__(self,_from,_to):
        self._from = _from
        self._to = _to
        self._color = 0

n = int(input()) - 1
e_all = []
max_b = 0
for i in range(n):
    a,b = map(int,input().split())
    e_all.append(edge(a-1,b-1))
    max_b =  max(b, max_b)

v = [[] for _ in range(max_b)]
for i in range(n):
    e = e_all[i]
    j = 0
    while True:
        if len(v[e._from]) <= j + 1:
            v[e._from].append(False)
        if v[e._from][j] == False:
            while len(v[e._to]) <= j + 1:
                v[e._to].append(False)
            if v[e._to][j] == False:
                v[e._from][j] = True
                v[e._to][j] = True
                e._color = j + 1
                break
        j += 1
cnt = []
for i in range(max_b):
    cnt.append(v[i].count(True))

print (max(cnt))
for i in range(n):
    print (e_all[i]._color)

Submission status: Wrong Answer

Solution code:
import sys,math

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())

def main():
	N = II()
	to = [[] for _ in range(N)]
	ans = {}
	for i in range(N-1):
		a,b = MI()
		a -= 1;b -= 1
		ans[str(a)+"-"+str(b)] = 0
		to[a].append(b);to[b].append(a)
	
	def bfs():
		from collections import deque
		que = deque()
		que.append(0)
		e_colors = [0]*N
		max_c = 0
		while len(que) > 0:
			n = que.popleft()
			for i in to[n]:
				if(e_colors[i]==0):
					ch = e_colors[n] | e_colors[i]
					index = int(math.log2(~ch & -~ch))
					e_colors[n] += 1 << index
					e_colors[i] += 1 << index
					ans[str(min(n,i))+"-"+str(max(n,i))] = index+1
					if(max_c < index+1): max_c = index+1
					que.append(i)
		print(max_c)
		for i in ans.values():
			print(i)

	bfs()

main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    use = [0 for _ in range(N)]
    dist = []
    c = [[] for i in range(N)]
    for i in range(N-1):
        a,b = map(int,input().split())
        use[a-1] += 1
        use[b-1] += 1
        dist.append((a-1,b-1))
        
    m = max(use)
    print(m)
    for a,b in dist:
        for i in range(1,m+1):
            if (i not in c[a] and i not in c[b]):
                print(i)
                c[a].append(i)
                c[b].append(i)
                break
        
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
dim = [0] * n
edges = []
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  dim[a] += 1
  dim[b] += 1
  edges.append((a,b))
print(max(dim))
idset = [set() for _ in range(n)]
for ed in edges:
  i = 1
  while i in idset[ed[0]] or i in idset[ed[1]]: i += 1
  print(i)
  idset[ed[0]].add(i)
  idset[ed[1]].add(i)

Submission status: Wrong Answer

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [0]*N
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		ch = e_colors[a] | e_colors[b]
		j = int(math.log2(~ch & -~ch))
		e_colors[a]+=(1<<j)
		e_colors[b]+=(1<<j)
		ans_colors.append(j+1)
		if(max_color < j+1):
			max_color = (j+1)
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i])

main()

Submission status: Wrong Answer

Solution code:
import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [0]*N
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		ch = e_colors[a] | e_colors[b]
		j = int(math.log2(~ch & -~ch))
		e_colors[a]+=(1<<j)
		e_colors[b]+=(1<<j)
		ans_colors.append(j+1)
		if(max_color < j+1):
			max_color = (j+1)
	print(e_colors)
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i])

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [0]*N
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		ch=0
		ch = e_colors[a] | e_colors[b]
		for j in range(max_color+1):
			if not (ch>>j)&1:
				e_colors[a]+=(1<<j)
				e_colors[b]+=(1<<j)
				ans_colors.append(j)
				if(max_color < j+1):
					max_color = (j+1)
				break
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i]+1)

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [[] for _ in range(N)]
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		ch=[False]*(max_color+1)
		for j in e_colors[a]:
			ch[j]=True
		for j in e_colors[b]:
			ch[j]=True
		for j in range(max_color+1):
			if(ch[j]==False):
				e_colors[a].append(j)
				e_colors[b].append(j)
				ans_colors.append(j)
				if(max_color < j+1):
					max_color = (j+1)
				break
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i]+1)

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [[] for _ in range(N)]
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		to[a].append(b)
		to[b].append(a)
		l = max(len(to[a]),len(to[b]))
		ch=[False]*(N-1)
		for j in e_colors[a]:
			ch[j-1]=True
		for j in e_colors[b]:
			ch[j-1]=True
		for j in range(N-1):
			if(ch[j]==False):
				e_colors[a].append(j+1)
				e_colors[b].append(j+1)
				ans_colors.append(j+1)
				if(max_color < j+1):
					max_color = (j+1)
				break
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i])

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [[] for _ in range(N)]
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		to[a].append(b)
		to[b].append(a)
		l = max(len(to[a]),len(to[b]))
		ch=[False]*(N-1)
		for j in e_colors[a]:
			ch[j-1]=True
		for j in e_colors[b]:
			ch[j-1]=True
		for j in range(N-1):
			if(ch[j]==False):
				e_colors[a].append(j+1)
				e_colors[b].append(j+1)
				ans_colors.append(j+1)
				if(max_color < j+1):
					max_color = j+1
				break
	print(l)
	for i in range(N-1):
		print(ans_colors[i])

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		to[a].append(b)
		to[b].append(a)
		l = max(len(to[a]),len(to[b]))
		e_colors.append(l)
		if(l>max_color):
			max_color = l
	print(l)
	for i in range(N-1):
		print(e_colors[i])

main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
g = [list(map(int,readline().split())) for i in range(n-1)]

color = [[] for i in range(n)] #各頂点が何色を使用済みなのか
ans = []
for i in g:
    for j in range(10**5):
        if not j in color[i[0]-1] and not j in color[i[1]-1]:
            ans.append(j+1)
            color[i[0]-1].append(j)
            color[i[1]-1].append(j)
            break

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ABs = [tuple(map(int, input().split())) for _ in range(n-1)]

vertex = [0 for _ in range(n)]
for ab in ABs:
    for v in ab:
        vertex[v-1] += 1
max_color = max(vertex)
print(max_color)
used_color = [[False for _ in range(max_color)] for _ in range(n)]
color = 0
for ab in ABs:
    color = used_color[ab[0]-1].index(False)
    print(color+1)
    for v in ab:
        used_color[v-1][color] = True

Submission status: Wrong Answer

Solution code:
n = int(input())
edge_list = [list(map(int, input().split())) for i in range(n-1)]

# 最大色数取得手順
# init dic
count_dic = {}
for i in range(n):
    count_dic[i+1] = 0

# count edge 
for edges in edge_list:
    for edge in edges:
        count_dic[edge] += 1

# 最大色数取得
K = max(count_dic.values())

# root決定(次数最大頂点)
K_V = [k for k, v in count_dic.items() if v == K][0]

# 木の構成
tree = {}
tree[K_V] = [edges[abs(edges.index(K_V) - 1)] for edges in edge_list if K_V in edges]

# 決定済み頂点
decided_v = []
decided_v.append(K_V)

# 幅優先探索
next_vs = tree[K_V]

# 最大色数頂点をrootにした木の構成
while len(tree.keys()) < n:
    under_vs = []
    for next_v in next_vs:
        tree[next_v] = [edges[abs(edges.index(next_v) - 1)] for edges in edge_list if next_v in edges and edges[abs(edges.index(next_v) - 1)] not in decided_v]
        for under_v in tree[next_v]:
            under_vs.append(under_v)
        decided_v.append(next_v)
    next_vs = under_vs

# 枝の色を決定していく
result_dic = {}
edges_idx = {}
all_edge = 0
for v, child_vs in tree.items():
    for child_v in child_vs:
        for color_num in range(1, K+1):
            flag = True
            for edge_idx in edges_idx.keys():
                if set(edges_idx[edge_idx]) & set([v, child_v]) == set([v]):
                    if result_dic[edge_idx] == color_num:
                        flag = False
                        break

            if flag:
                result_dic[all_edge + 1] = color_num
                edges_idx[all_edge + 1] = set([v, child_v])
                all_edge += 1
                break

print(K)
for color_num in result_dic.values():
    print(color_num)

Submission status: Wrong Answer

Solution code:
n = int(input())
edge_list = [list(map(int, input().split())) for i in range(n-1)]

# 最大色数取得手順
# init dic
count_dic = {}
for i in range(n):
    count_dic[i+1] = 0

# count edge 
for edges in edge_list:
    for edge in edges:
        count_dic[edge] += 1

# 最大色数取得
K = max(count_dic.values())

# root決定(次数最大頂点)
K_V = [k for k, v in count_dic.items() if v == K][0]

# 木の構成
tree = {}
tree[K_V] = [edges[abs(edges.index(K_V) - 1)] for edges in edge_list if K_V in edges]

# 決定済み頂点
decided_v = []
decided_v.append(K_V)

# 幅優先探索
next_vs = tree[K_V]

# 最大色数頂点をrootにした木の構成
while len(tree.keys()) < n:
    under_vs = []
    for next_v in next_vs:
        tree[next_v] = [edges[abs(edges.index(next_v) - 1)] for edges in edge_list if next_v in edges and edges[abs(edges.index(next_v) - 1)] not in decided_v]
        for under_v in tree[next_v]:
            under_vs.append(under_v)
        decided_v.append(next_v)
    next_vs = under_vs

# 枝の色を決定していく
result_dic = {}
edges_idx = {}
all_edge = 0
for v, child_vs in tree.items():
    for child_v in child_vs:
        for color_num in range(1, K+1):
            flag = True
            for edge_idx in edges_idx.keys():
                if set(edges_idx[edge_idx]) & set([v, child_v]) == set([v]):
                    if result_dic[edge_idx] == color_num:
                        flag = False
            if flag:
                result_dic[all_edge + 1] = color_num
                edges_idx[all_edge + 1] = set([v, child_v])
                all_edge += 1
                break

print(K)
for color_num in result_dic.values():
    print(color_num)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

N=int(input())

q=[]

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

ans=[1]*N
ans[0]=0
#print(l)

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

mx=0
for index,item in enumerate(l):
    color=1
    while item:
        temp=item.pop(-1)
        if color==ans[index]:
            color+=1
        ans[temp]=color
        color+=1
    mx=max(color-1,mx)

print(mx)
for item in ans[1:]:
    print(item)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = {}
C = []
for _ in range(N-1):
    r = []
    a,b = [int(i) for i in input().rstrip().split(' ')]
    if not a in P:
        P[a] = 1
    if not b in P:
        P[b] = 1
    #print(P)
    for c in range(1,N+1):
        c1 = 1<<c
        #print([bin(i) for i in [c1,P[a],P[b],P[a]|P[b]]])
        if c1&(P[a]|P[b]) == 0:
            P[a] |= c1
            P[b] |= c1
            C += [c]
            break
print(max(C))
print(*C, sep='\n')

Submission status: Wrong Answer

Solution code:
N = int(input())
P = {}
C = []
for _ in range(N-1):
    r = []
    a,b = [int(i) for i in input().rstrip().split(' ')]
    if not a in P:
        P[a] = []
    if not b in P:
        P[b] = []
    #print(P)
    for c in range(1,N+1):
        if not c in P[a]+P[b]:
            P[a] += [c]
            P[b] += [c]
            C += [c]
            break
print(max(C))
print(*C, sep='\n')

Submission status: Wrong Answer

Solution code: