Problem:


Score : 400 points

Problem Statement

Given is a tree G with N vertices.
The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.

Consider painting the edges in G with some number of colors.
We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.

Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.

Constraints

 2 \le N \le 10^5

 1 \le a_i \lt b_i \le N

All values in input are integers.

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print N lines.

The first line should contain K, the number of colors used.

The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.

If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.

Sample Input 1

3
1 2
2 3

Sample Output 1

2
1
2

Sample Input 2

8
1 2
2 3
2 4
2 5
4 7
5 6
6 8

Sample Output 2

4
1
2
3
4
1
1
2

Sample Input 3

6
1 2
1 3
1 4
1 5
1 6

Sample Output 3

5
1
2
3
4
5



Sample input:
3
1 2
2 3


Sample output:
2
1
2

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]

    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    queue = deque([0])
    parent = [0] * N
    parent[0] = -1
    order = []

    while queue:
        v = queue.popleft()
        order.append(v)
        for nv in G[v]:
            if nv == parent[v]:
                continue
            parent[nv] = v
            queue.append(nv)

    color = [0] * N
    color[0] = 1
    for v in order:
        c = 1
        for nv in G[v]:
            if nv == parent[v]:
                continue
            if c == color[parent[v]]:
                c += 1
            color[nv] = c
            c += 1

    ans = []
    for a, b in zip(*[iter(AB)] * 2):
        if parent[a - 1] == b - 1:
            ans.append(color[a - 1])
        else:
            ans.append(color[b - 1])

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  l[a]+=1
  l[b]+=1
c=max(l)
print(c)
for i in range(1,n):
  if i%c==0:
    print(c)
  else:
    print(i%c)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import deque
        
n = int(input())
uf = UnionFind(n)
g = [[] for i in range(n)]
cnt = [0] * n
ans = [0] * (n - 1)
ans_index = []

for i in range(n - 1):
    a, b = map(lambda x:int(x) - 1, input().split())
    uf.union(a, b)
    g[a].append(b)
    g[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
    ans_index.append((a, b))
    

for i in uf.roots():
    visited = [0] * n
    visited[i] = 1
    que = deque()
    que.append([i, 0])
    while que:
        s = que.popleft()
        k = 0
        for j in g[s[0]]:
            if not visited[j]:
                while True:
                    k += 1
                    if k != s[1]:
                        que.append([j, k])
                        visited[j] = 1
                        #ans[ans_index.index((s[0], j))] = k
                        break

print(max(cnt))
print(*ans, sep = "\n")

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt = [0] * n
ans = []
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    cnt[a] += 1
    cnt[b] += 1
    ans.append(max(cnt[a], cnt[b]))

print(max(cnt))
print(*ans, sep = "\n")

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))

mod = pow(10,9)+7
ok = 1

import math

for a in A:
    ok = ok*a//math.gcd(a,ok)

LCM = ok



counter = 0
for a in A:
    counter += LCM//a
    counter %= mod 

print(counter)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
edges = [[] for _ in range(N)]
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])
# for i in edges:
#     print(i)
q = collections.deque()
q.append([0,1,0])
colors = [0]*(N-1)
check = [0]*N
while len(q) != 0:
    v, color, num = q.popleft()
    check[v] = 1
    # print(v,color,num)
    if colors[num] == 0:
        colors[num] = color
    next_color = 0
    for w in edges[v]:
        if check[w[0]] != 0:
            continue
        next_color += 1
        if next_color == colors[num]:
            next_color += 1
        q.append([w[0],next_color,w[1]])
print(len(set(colors)))
for i in colors:
    print(i)

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque
from collections import defaultdict

n = int(input())
graph = defaultdict(list)
ab = []

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

max_c = max([len(x) for x in list(graph.values())])

colors = set(range(1, max_c + 1))

ans = [0] * (n - 1)

q = deque([1])

while q:
    curr = q.popleft()
    can_use = copy.deepcopy(colors)
    for x in graph[curr]:
        if curr > x:
            can_use -= set([min(can_use)])
    for x in graph[curr]:
        if curr < x:
            color = min(can_use)
            ans[ab.index((curr, x))] = color
            can_use -= set([color])
            q.append(x)

print(max_c)
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
node_branch = [[] for _ in range(N+1)]
branch = [0] * (N)
link = [0] * (N+1)
checked = [False] * (N+1)

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

maxlen = 0
for i, node in enumerate(node_branch):
    if maxlen < len(node):
        maxlen = len(node)
        maxnode = i + 1

print(maxlen)

d = deque()
d.append(maxnode)
link[1] = 0
checked[maxnode] = True

while len(d)>0:
    now = d.popleft()
    color = 1
    for n, b in node_branch[now]:
        if checked[n]:
            continue
        if color == link[now]:
            color += 1
        branch[b] = color
        link[n] = color
        checked[n] = True
        d.append(n)

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

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())
adj = collections.defaultdict(list)
edges = []
for _ in range(n - 1):
	u,v = map(int, raw_input().split(' '))
	edges.append((u,v))
	adj[u].append(v)
	adj[v].append(u)
root = 1
q = collections.deque([root])
h = {}
while(q):
	u = q.popleft()
	c = 1

	used = set([h[tuple(sorted([u,v]))] for v in adj[u] if tuple(sorted([u,v])) in h]) 

	for v in adj[u]:
		t = tuple(sorted([u,v])) 
		if t not in h:
			while(c in used): c+=1
			h[t] = c	
			c+=1
			q.append(v)
for u,v in edges:
	print h[(u,v)]

Submission status: Wrong Answer

Solution code:
n=int(input())
color=[[] for i in range(n)]
color_v=set(range(1,n))
res=[0]*(n-1)
for i in range(n-1):
  a,b=map(int,input().split())
  set_c=list(color_v - set(color[a-1]+color[b-1]))[0]
  color[a-1].append(set_c)
  color[b-1].append(set_c)
  res[i]=set_c
print(max(res))
for i in range(n-1):
  print(res[i])

Submission status: Wrong Answer

Solution code:
##かっこいい実装
import numpy as np
#mod = 10**9+7
#n = int(input())
#a = np.fromstring(input(), dtype = np.int64, sep = ' ')
#
#result = 0
#for i in range(60):
#    count_one = int((a&1).sum())
#    result += count_one*(n-count_one)*(2**i)
#    a >>= 1
#print(result%mod)

N = int(input())
A = np.fromstring(input(),dtype = np.int64, sep = ' ')
Large = 10**9 + 7
ans = 0
for i in range(60):
    sum1 = np.sum(A&1)
    ans += sum1*(N-sum1) * pow(2,i,Large)
    A>>=1 # A = A>>1とする
print(ans)

Submission status: Wrong Answer

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

'''

'''

from collections import deque

def get_color(g, colors, node):
    col_seen = set()
    for nb in g[node]:
        col_seen.add(colors[nb])

    col = 1
    while col in col_seen:
        col += 1

    return col


def solve(n, g):
    num_cols = 0
    colors = [0] * n
    nodes = deque([0])
    visited = [0] * n
    visited[0] = 1

    while nodes:
        node = nodes.popleft()

        col_seen = set()
        for nb in g[node]:
            
            # Add to queue
            if not visited[nb]:
                nodes.append(nb)
                visited[nb] = 1
            
            col_seen.add(colors[nb])
        
        # Find and set col
        col = 1
        while col in col_seen:
            col += 1
        
        num_cols = max(num_cols, col)
        colors[node] = col

    return num_cols, colors



n = int(input())
num_edges = [0 for _ in range(n)]
#cols_num = [1] * n
cols_group = [set() for _ in range(n)]

edges = []
for _ in range(n-1):
    a, b = map(lambda x: int(x) - 1, input().split())
    num_edges[a] += 1
    num_edges[b] += 1
    edges.append((a, b))

num_cols = max(v for v in num_edges)
i = 0
print(num_cols)
for a, b in edges:
    col = 1 if i % 2 == 0 else num_cols
    inc = 1 if i % 2 == 0 else -1
    while col in cols_group[a] or col in cols_group[b]:
        col += inc
    print(col)
    cols_group[a].add(col)
    cols_group[b].add(col)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction



def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num - 1)]

    node_data = defaultdict(set)
    for i in range(num - 1):
        a, b = data[i]
        node_data[a].add(b)
        node_data[b].add(a)

    ans_num = 0
    for i in range(1, num + 1):
        ans_num = max(ans_num, len(node_data[i]))

    edge_data = defaultdict(int)
    ans_count = 0
    for i in range(1, num + 1):
        now_list = list(node_data[i])
        now_list.sort()
        count = bisect.bisect_left(now_list, i) + 1
        for ele in now_list[count - 1:]:
            edge_data[(i, ele)] = count
            edge_data[(ele, i)] = count
            count += 1
        ans_count = max(ans_count, count - 1)

    print(ans_count)
    for i in range(num - 1):
        a, b = data[i]
        ans = edge_data[(a, b)]
        print(ans)








if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

n = int(input())
de = {}
dn = {}
max = 0

for i in range(n-1):
    te = list(map(int, input().split()))
    de.setdefault(i, te)
    if te[0] in dn:
        dn[te[0]]+=1
    else:
        dn.setdefault(te[0], 1)
    if te[1] in dn:
        dn[te[1]]+=1
    else:
        dn.setdefault(te[1], 1)

#print(de)
#print(dn)

for i in range(1, len(dn)+1):
    if dn[i] > max:
        max = dn[i]
    dn[i]=0

print(max)

for i in range(len(de)):
    a = dn[de[i][0]]
    b = dn[de[i][1]]
    if a < b:
        print(b%max+1)
        dn[de[i][0]]=b+1
        dn[de[i][1]]=b+1
    else:
        print(a%max+1)
        dn[de[i][0]]=a+1
        dn[de[i][1]]=a+1
    #print(dn)

Submission status: Wrong Answer

Solution code:
n = int(input())
iro = [set() for i in range(n)]
ans = [0 for i in range(n)]
cou = 1
for i in range(n-1):
    a,b = map(int,input().split())
    now = 1
    while True:
        if (not now in iro[a-1]) and (not now in iro[b-1]):
            ans[cou] = now
            cou += 1
            iro[a-1].add(now)
            iro[b-1].add(now)
            break
        else:
            now += 1
ans[0] = max(ans)
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
adj = [[] for _ in range(N+1)]
edge = {}
for i in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
    edge[(a, b)] = i
    edge[(b, a)] = i
print(adj)
print(edge)

que = deque()
que.append(1)
seen = [-1] * (N+1)
seen[1] = 0
ans = [0] * (N-1)
while que:
    v = que.pop()
    j = 1
    for u in adj[v]:
        if seen[u] < 0:
            if j == seen[v]:
                j += 1
            seen[u] = j
            ans[edge[(u, v)]] = j
            que.appendleft(u)
            j += 1

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
E = {}
for i in range(N):
  E[i] = []
  
for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1, b-1
  # 出力のために、何番目のEdgeだったかを保有させる必要がある
  E[a].append([i,b])
  E[b].append([i,a])
  
k = 0
for keys, v in E.items():
  k = max(k, len(v))
print(k)

colors = [-1 for i in range(N-1)]
visited = [False for i in range(N)]
d = deque()

d.append([0, -1])
#print(E)
while len(d) > 0:
  p,c = d.pop()
  visited[p] = True
  color = 1
  if c == color:
    color += 1
  for i, nxt in E[p]:
    #print(i, nxt, visited[i], colors[i])
    if visited[nxt]:
      continue # TreeでBFSだとここは通らない・・・？
    if colors[i] > -1:
      continue
    colors[i] = color
    d.append([nxt, color])
    color += 1
    if c == color:
      c += 1
      
for i in range(len(colors)):
  print(colors[i])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append((b,i))
        adj[b].append((a,i))
    p = max([len(a) for a in adj])
    ans = [-1] * (N-1)
    visited = [-1] * N
    visited[0] = 0
    q = deque([0])
    
    while q:
        now = q.popleft()
        tmp = 0
        for v in adj[now]:
            if visited[v[0]] < 0:
                q.append(v[0])
                ans[v[1]] = (tmp+1) % p
                tmp += 1
                visited[v[0]] = 0
                if ans[v[1]] == 0:
                    ans[v[1]] += p
            else:
                tmp = ans[v[1]]
    print(p)
    [print(a) for a in ans]

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import deque

def main():
    N = int(input())
    adj = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append((b,i))
        adj[b].append((a,i))
    p = max([len(a) for a in adj])
    ans = [-1] * (N-1)
    visited = [-1] * N
    ans[0] = 1
    q = deque([0])
    
    while q:
        now = q.popleft()
        tmp = 1
        for v in adj[now]:
            if visited[v[0]] < 0:
                q.append(v[0])
                ans[v[1]] = (tmp + 1) % p
                tmp += 1
                visited[v[0]] = 0
                if ans[v[1]] == 0:
                    ans[v[1]] += p
            else:
                tmp = ans[v[1]]
    print(p)
    [print(a) for a in ans]

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for i in range(n+1)]
d = {}
l = [-1] * (n-1)
max_idx = 0
for i in range(n-1):
  u,v = map(int, input().split())
  d[(u,v)] = i
  d[(v,u)] = i
  g[u].append((u,v))
  g[v].append((v,u))
  if len(g[max_idx]) < len(g[u]):
    max_idx = u
  if len(g[max_idx]) < len(g[v]):
    max_idx = v
m = len(g[max_idx])
stack = []
while len(g[1]) > 0:
  stack.append(g[1].pop())
while len(stack) > 0:
  u, v = stack.pop()
  #print(u,v)
  if len(g[v]) > 0:
    count = m
    while len(g[v]) > 0:
      u2, v2 = g[v].pop()
      if count == l[d[(u, v)]]:
        count -= 1
      if l[d[(u2, v2)]] == -1:
        l[d[(u2, v2)]] = count
        count -= 1
        stack.append((u2, v2))
print(m)
for i in range(n-1):
  print(l[i])

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for i in range(n+1)]
d = {}
l = [-1] * (n-1)
max_idx = 0
for i in range(n-1):
  u,v = map(int, input().split())
  d[(u,v)] = i
  d[(v,u)] = i
  g[u].append((u,v))
  g[v].append((v,u))
  if len(g[max_idx]) < len(g[u]):
    max_idx = u
  if len(g[max_idx]) < len(g[v]):
    max_idx = v
m = len(g[max_idx])
stack = []
while len(g[1]) > 0:
  stack.append(g[1].pop())
while len(stack) > 0:
  u, v = stack.pop()
  #print(u,v)
  if len(g[v]) > 0:
    count = m
    while len(g[v]) > 0:
      u2, v2 = g[v].pop()
      if count == l[d[(u, v)]]:
        count -= 1
      if l[d[(u2, v2)]] == -1:
        l[d[(u2, v2)]] = count
        count -= 1
        stack.append((u2, v2))
#print(m)
for i in range(n-1):
  print(l[i])

Submission status: Wrong Answer

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

from collections import defaultdict
g = defaultdict(list)
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

k = 0
for key in g:
    k = max(k, len(g[key]))
print(k)

ans = dict()
q = [(0, -1)] # (pos, used_color)
visited = set([0])
while q:
    cur, col = q.pop()

    if col == 0:
        tmp = 1
    else:
        tmp = 0

    for target in g[cur]:
        if target not in visited:
            q.append((target, tmp))
            visited.add(target)
            ans[(cur, target)] = tmp
            tmp += 1

for a, b in ab:
    key = (a-1, b-1)
    print(ans[key] + 1)

Submission status: Wrong Answer

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

q = deque([(0,-1,-1)])
colors = [None] * N
while q:
  new_q = deque([])
  L = len(q)
  for _ in range(L):
    n,c,pc = q.popleft()
    colors[n] = c

    if c == -1 or c > 1:
      nc = 1
    elif c == 1:
      nc = 2
    for nei in adj[n]:
      new_q.append((nei,nc,c))
      nc += 1
      if nc == c: nc += 1

  q = new_q

print(len(set(colors[1:])))
for c in colors[1:]:
  print(c)

Submission status: Wrong Answer

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

# node, last_color
q = deque([(0,-1,-1)])
colors = [None] * N
while q:
  new_q = deque([])
  L = len(q)
  for _ in range(L):
    n,c,pc = q.popleft()
    colors[n] = c

    if c == -1 or c > 1:
      nc = 1
    elif c == 1:
      nc = 2
    for nei in adj[n]:
      new_q.append((nei,nc,c))
      nc += 1
      if nc == pc: nc += 1

  q = new_q

print(len(set(colors[1:])))
for c in colors[1:]:
  print(c)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from copy import deepcopy

input=sys.stdin.readline
N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[set() for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
di=dict()

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

v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      v.append(item)
      st=str(k)+","+str(item)
      di[st] = s
#      
#print(maxi)
#for i in range(N-1):
#  t_str = str(a[i]-1)+","+str(b[i]-1)
#  print(di[t_str])

Submission status: Wrong Answer

Solution code:
n=int(input())
ki=[[] for _ in range(n)]
hen=[tuple(map(int,input().split())) for i in range(n-1)]
color={(hen[i][0]-1,hen[i][1]-1):0 for i in range(n-1)}
for i in range(n-1):
  a,b=hen[i][0],hen[i][1]
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
mcol=0
ne=0
for i in range(n):
  if len(ki[i])>mcol:
    mcol=len(ki[i])
    ne=i
print(mcol)
from collections import deque
d=deque()
d.append(ne)
visited=[False]*n
visited[ne]=True
col=[0]*n
while d:
  g=d.popleft()
  for i in ki[g]:
    if visited[i]:
      continue
    d.append(i)
    visited[i]=True
    if g>i:
      x,y=i,g
    else:
      x,y=g,i
    color[(x,y)]=col[g]%mcol+1
    col[g],col[i]=color[(x,y)],color[(x,y)]
print(*color.values())

Submission status: Wrong Answer

Solution code:
N = int(input())
K = 0
edge = [[] for i in range(N)]
ans = []
for i in range(N-1):
    a,b = map(int,input().split(' '))
    m = min(list(set(list(range(1,K+2)))-set(edge[a-1]+edge[b-1])))
    ans.append(m)
    edge[a-1].append(m)
    edge[b-1].append(m)
    K =max(K,m)
print(K)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      e[item] = e[k]+1
      v.append(item)
      s=pos.pop()
      c[k].add(s)
      c[item].add(s)
      
print(maxi)
for i in range(N-1):
  pass
  #print( g[a[i]-1][b[i]-1] )

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      e[item] = e[k]+1
      v.append(item)
      s=pos.pop()
      c[k].add(s)
      c[item].add(s)
      
print(maxi)
for i in range(N-1):
  pass
  #print( g[a[i]-1][b[i]-1] )

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  #maxi=max(maxi,len(d[k]))
  #all=set(i+1 for i in range(len(d[k])))
  #pos=deepcopy(all)
  #pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      #s=min(pos)
      #c[k].add(s)
      #c[item].add(s)
      #pos.remove(s)
      e[item] = e[k]+1
      #g[k][item]=s
      #g[item][k]=s
      v.append(item)
      
print(maxi)
for i in range(N-1):
  pass
  #print( g[a[i]-1][b[i]-1] )

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
#g=[[ 0 for _ in range(N)] for _ in range(N)]

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  #maxi=max(maxi,len(d[k]))
  #all=set(i+1 for i in range(len(d[k])))
  #pos=deepcopy(all)
  #pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      #s=min(pos)
      #c[k].add(s)
      #c[item].add(s)
      #pos.remove(s)
      e[item] = e[k]+1
      #g[k][item]=s
      #g[item][k]=s
      v.append(item)
      
print(maxi)
for i in range(N-1):
  pass
  #print( g[a[i]-1][b[i]-1] )

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

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

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      #s=min(pos)
      #c[k].add(s)
      #c[item].add(s)
      #pos.remove(s)
      e[item] = e[k]+1
      #g[k][item]=s
      #g[item][k]=s
      v.append(item)
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )

Submission status: Wrong Answer

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

que=deque([0])
ans=[0]*(n-1)
par=[0]*n
par[0]=-1
while que:
    x=que.popleft()
    p=par[x]
    color=1
    for tup in arr[x]:
        if p==color:
            color+=1
        if ans[tup[1]]==0:
            ans[tup[1]]=color
            par[tup[0]]=color
            color+=1
            que.append(tup[0])
print(max(ans))
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
N=int(input())

col=[set() for _ in range(N)]
ans=[]

for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    for j in range(1,N+1):
        if j not in col[a] and j not in col[b]:
            break
    ans.append(j)
    col[a].add(j)
    col[b].add(j)

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

Submission status: Wrong Answer

Solution code:
N=int(input())
K=0

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

for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    j=1
    while True:
        if j not in node[a] and j not in node[b]:
            break
        j+=1
    ans.append(j)
    node[a].append(j)
    node[b].append(j)

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

Submission status: Wrong Answer

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
ab=t3(n-1)

d={i:[] for i in range(1,n+1)}
for a,b in ab:
    d[a].append(b)
#     d[b].append(a)

l=list(d.items())
# l.sort(key=lambda x:-len(x[1]))
# m=len(l[0][1])
m=0
d2={line:0 for line in ab}
c={i:[] for i in range(1,n+1)}
for a,list1 in l:
    m=max(m,len(list1))
    color=1
    for b in list1:
#         if a1>b1:
#             a,b=b1,a1
#         else:
#             a,b=a1,b1
#         print(a,b)
#         if d2[(a,b)]!=0:
#             continue
#         else:
        while color in c[a] or color in c[b]:
            color+=1 
        d2[(a,b)]=color
        c[a].append(color)
        c[b].append(color)
        color+=1
#     print(d2)
print(m)
ans=[]
for line in ab:
    ans.append(d2[line])
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    x = [0 for _ in range(n + 1)]
    y = [False for _ in range(n + 1)]
    z = [0 for _ in range(n)]
    for k in range(1, n):
        i, j = map(int, input().split())
        x[i] += 1
        x[j] += 1
        m = max(x[i], x[j])

        if m > 2:
            z[k] = max(x[i], x[j])
            y[i] = not y[i]
            y[j] = not y[j]
        elif (x[i], x[j]) == (1, 1):
            z[k] = 1
            y[i] = not y[i]
            y[j] = not y[j]
        elif (x[i], x[j]) == (1, 2):
            z[k] = int(y[j]) + 1
            y[i] = not y[j]
        elif (x[i], x[j]) == (2, 1):
            z[k] = int(y[i]) + 1
            y[j] = not y[i]

    z[0] = max(x)
    ans = '\n'.join(map(str, z))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 連想配列
from collections import deque
N = int(input())
ab = {}
path = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)
    ab[(a-1,b-1)] = 0
color = [0]*N
color[0] = -1
q = deque([])
q.append(0)
max = 0

while len(q)>0:
    cn = q.popleft()
    ccolor = color[cn]
    ncolor = 1
    for i in path[cn]:
        if color[i] == 0:
            if ccolor != ncolor:
                color[i] = ncolor
                ab[(cn,i)] = ncolor
                ncolor += 1
            else:
                color[i] = ncolor+1
                ab[(cn,i)] = ncolor+1
                ncolor += 2
            if color[i] > max:
                max = color[i]
            q.append(i)
print(max)
for i,j in ab.items():
    print(j)

Submission status: Wrong Answer

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

for i in range(N-1):
    a,b = ab[i]
    for j in range(1, 10**5):
        if j not in color[a-1] and j not in color[b-1]:
            ncolor = j
            break
    ans[i] = ncolor
    color[a-1].append(ncolor)
    color[b-1].append(ncolor)
print(max(ans))
for i in ans:
    print(i)