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: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10000)
sys.set
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

print(max([len(d) for d in D]))

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
D = [deque([]) for _ in range(N)]
cnt = 0
AB = [0] * (N-1)
dic = {}
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    AB[n] = (a-1, b-1)
    dic[(a, b)] = 0
    D[a-1].append(b-1)
    D[b-1].append(a-1)

print(max([len(d) for d in D]))

def dp(pp, p, c):
    global dic
    nc = 1
    for np in D[p]:
        if np == pp:
            continue
        if nc == c:
            nc += 1
        dic[(p, np)] = nc
        dp(p, np, nc)
        nc += 1
    return 0

dp(-1, 0, 0)
for ab in AB:
    print(dic[ab])

Submission status: Runtime Error

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

count_list = [0 for _ in range(n)]

for edge in edges:
    count_list[edge[0]-1] += 1
    count_list[edge[1]-1] += 1

color_count = max(count_list)

def exception(array1,array2,color_count):
    for num in list(range(color_count)):
        if num not in array1 and num not in array2:
            return num
    return None

edge_list = []
node_dict = {}
for i in range(n):
    node_dict[i] = []
for edge in edges:
    color = exception(node_dict[edge[0]-1],node_dict[edge[1]-1],color_count)
    node_dict[edge[0]-1].append(color)
    node_dict[edge[1]-1].append(color)
    edge_list.append(color)

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

Submission status: Runtime Error

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

count_list = [0 for _ in range(n)]

for edge in edges:
    count_list[edge[0]-1] += 1
    count_list[edge[1]-1] += 1

color_count = max(count_list)

def exception(array1,array2,color_count):
    for num in list(range(color_count)):
        if num not in array1 and num not in array2:
            return num
    return None

edge_list = []
node_dict = {}
for i in range(n):
    node_dict[i] = []
for edge in edges:
    color = exception(node_dict[edge[0]-1],node_dict[edge[1]-1],color_count)
    node_dict[edge[0]-1].append(color)
    node_dict[edge[1]-1].append(color)
    edge_list.append(color)

print(color_count)
for i in range(n-1):

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class G:
    def __init__(self):
        self.edges = defaultdict(list)
        self.N = int(input())
        self.edge_numbers = {}
        for i in range(self.N - 1):
            a, b = map(int, input().split())
            self.edges[a - 1].append(b - 1)
            self.edges[b - 1].append(a - 1)
            self.edge_numbers[i] = (a - 1, b - 1)

        self.K = max(len(self.edges[v]) for v in self.edges.keys())

        self.visited = set()
        self.levels = defaultdict(int)
        self.painted = defaultdict(int)

    def paint(self, v, color, level):
        if v in self.visited:
            return
        self.levels[v] = level
        self.visited.add(v)

        paint_color = 1        
        for e in self.edges[v]:
            if e in self.visited:
                continue
            if paint_color == color:
                paint_color += 1
            self.painted[e] = paint_color
            self.paint(e, paint_color, level + 1)
            paint_color += 1


    def print(self):
        print(self.K)
        for i in range(len(self.edge_numbers)):
            a, b = self.edge_numbers[i]
            color = -1
            if self.levels[a] < self.levels[b]:
                color = self.painted[b]
            else:
                color = self.painted[a]
            print(color)

g = G()
g.paint(0, 0, 0)
g.print()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class G:
    def __init__(self):
        self.edges = defaultdict(list)
        self.N = int(input())
        self.edge_numbers = {}
        for i in range(self.N - 1):
            a, b = map(int, input().split())
            self.edges[a - 1].append(b - 1)
            self.edges[b - 1].append(a - 1)
            self.edge_numbers[i] = (a - 1, b - 1)

        self.K = max(len(self.edges[v]) for v in self.edges.keys())

        self.visited = []
        self.levels = defaultdict(int)
        self.painted = defaultdict(int)

    def paint(self, v, color, level):
        if v in self.visited:
            return
        self.levels[v] = level
        self.visited.append(v)

        paint_color = 1        
        for e in self.edges[v]:
            if e in self.visited:
                continue
            if paint_color == color:
                paint_color += 1
            self.painted[e] = paint_color
            self.paint(e, paint_color, level + 1)
            paint_color += 1


    def print(self):
        print(self.K)
        for i in range(len(self.edge_numbers)):
            a, b = self.edge_numbers[i]
            color = -1
            if self.levels[a] < self.levels[b]:
                color = self.painted[b]
            else:
                color = self.painted[a]
            print(color)

g = G()
g.paint(0, 0, 0)
g.print()

Submission status: Runtime Error

Solution code:
N=int(input())
v=[[] for i in range(N)]
r=list()

def wps(s,d,u):
  c=1
  for i in range(len(v[d])):
    if v[d][i][0]!=s:
      c=c if u!=c else c+1
      v[d][i][1]=c
      wps(d,v[d][i][0],c)
      c+=1
    else:
      v[d][i][1]=u


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

wps(-1,0,-1)

m=0
for i in range(N):
  for j in range(len(v[i])):
    if i<v[i][j][0]:
      r.append(v[i][j])
  m=max(m,len(v[i]))

print(m)
r.sort(key=lambda x:x[2])
for e in r:
	print(e[1])

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
from collections import defaultdict as ddict
import numpy as np
R_children = ddict(set)
R_parents = ddict(set)
for ab in AB:
    R_children[ab[0]].add(ab[1])
    R_parents[ab[1]].add(ab[0])
ans = [0] * (N-1)
for i in range(N-1):
    used = set()
    for parent in R_parents[AB[i][0]]:
        color = ans[np.where(np.array(AB)[:,1]==AB[i][0])[0][0]]
        if color != 0:
            used.add(color) 
    for child in R_children[AB[i][1]]:
        color = ans[np.where(np.array(AB)[:,1]==child)[0][0]]
        if color != 0:
            used.add(color) 
    for child in R_children[AB[i][0]]:
        color = ans[np.where(np.array(AB)[:,1]==child)[0][0]]
        if color != 0:
            used.add(color) 
    if used == set():
        ans[i] = 1
    else:
        ans[i] = min(set(range(1,max(used)+2)) - used)
print(max(ans))
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    AB.append([int(i) for i in input().split()])
ans = [0]*(N-1)
ans[0] = 0
for i,ab in enumerate(AB):
    if i==0:
        pass
    else:
        used = set()
        AB_temp = AB[0:i]
        for  j,ab_temp in enumerate(AB_temp):
            if ab_temp[0] == ab[0] or ab_temp[0] == ab[1] or ab_temp[1] == ab[0] or ab_temp[1] == ab[1]:
                used.add(ans[j])
        ans[i] = min(set(range(max(used) + 2)) - used)
print(max(ans)+1)
for a in ans:
    print(a+1)

Submission status: Runtime Error

Solution code:
import os
import numpy as np

class getStdin(object):
    @classmethod
    def get_int(self):
        return int(input())

    @classmethod
    def get_ss_int(self):
        return list(map(int, input().split()))

class funcDfs(object):

    SEEN = list()

    def __init__(self, n, l):
        self.l = l
        self.graph = dict()
        for i in range(1, n+1):
            self.graph[i] = list()

        for li in l:
            a = li[0]
            b = li[1]
            self.graph[a].append(b)
            self.graph[b].append(a)

        self.SEEN = [False]*n
        self.color = dict()


    def dfs(self, v):
        self.SEEN[v-1] = True

        for i in self.graph[v]:
            mi = min(i, v)
            ma = max(i, v)
            tu = (mi, ma)

            if tu not in self.color.keys():
                al = list()
                for t in [x for x in self.color.keys() if v in x]:
                    al.append(self.color[t])

                if len(al) != 0:
                    al.sort()
                    for i in range(1, al[-1]+2):
                        if i not in al:
                            break

                else:
                    i = 1

                self.color[tu] = i

        for i in self.graph[v]:
            if self.SEEN[i-1]:
                continue

            self.dfs(i)

        return


if __name__ == '__main__':
    n = getStdin.get_int()
    l = list()
    for _ in range(n-1):
        l.append(getStdin.get_ss_int())

    df = funcDfs(n, l)
    df.dfs(1)
    print(max(df.color.values()))
    for i in l:
        i.sort()
        print(df.color[tuple(i)])

    #print(df.color)
    os.sys.exit(0)

Submission status: Runtime Error

Solution code:
## D - Coloring Edges on Tree
# 解説を元に作ったもの
def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(G[v])):
        u, ei = G[v][i]
        if u == p:
            continue
        if k == c:
            k += 1
            
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)
            

N = int(input())
G = [[] * N for _ in range(N)]
ans = [0] * N
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))
    
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(G[i]))
print(mx)
for i in range(N - 1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())

M = [set() for _ in range(N)]

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

def dfs(x, p, pre):
    cnt = 1
    for a in A[x]:
        if a[0] == pre:
            continue

        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

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

Submission status: Runtime Error

Solution code:
N = int(input())

M = [set() for _ in range(N)]

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

def dfs(x, p, pre):
    for a in A[x]:
        if a[0] == pre:
            continue

        cnt = 1
        if cnt == p:
            cnt += 1
        ans[a[1]] = cnt
        cnt += 1

        dfs(a[0], ans[a[1]], x)

dfs(0, -1, -1)

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

Submission status: Runtime Error

Solution code:
n = int(input())
vs = [[] for i in range(n)]
out = [0]*n

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

nex = [[0,-1]]

def coloring(index,defColor):
    i=0
    for v in vs[index]:
        if i==defColor:
           i+=1
        out[v[1]]=i
        vs[v[0]].remove([index,v[1]])
        nex.append([v[0],i])
        i+=1
    out[0] = max(out[0],i-1)

while nex.__len__()>0:
    c,d = nex.pop()
    coloring(c,d)

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

Submission status: Runtime Error

Solution code:
n = int(input())
vs = [[] for i in range(n)]
out = [0]*n

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

def coloring(index,defColor):
    i=0
    for v in vs[index]:
        if i==defColor:
           i+=1
        out[v[1]]=i
        vs[v[0]].remove([index,v[1]])
        coloring(v[0],i)
        i+=1
    out[0] = max(out[0],i-1)

coloring(0,-1)
for i in range(n):
    print(out[i]+1)

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[] for j in range(n)]
t=[]
for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1
"""
    buf = min(set(m)^set(l[a]+l[b]))
    l[a].append(buf)
    l[b].append(buf)
    """

    k=int(0)
    while True:
        if (k in l[a])==False:
            if (k in l[b])==False:
                l[a].append(k)
                l[b].append(k)
                break
            else:
                k +=1
        else:
            k +=1

    t.append(k+1)
    #m.append(i+1)
print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[] for j in range(n)]
t=[]
for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1
"""
    buf = min(set(m)^set(l[a]+l[b]))
    l[a].append(buf)
    l[b].append(buf)
    """

    k=int(0)
    while True:
        if (k in l[a])==False:
            if (k in l[b])==False:
                l[a].append(k)
                l[b].append(k)
                break
            else:
                k +=1
        else:
            k +=1

    t.append(t+1)
    #m.append(i+1)
print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[] for j in range(n)]
t=[]
for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1
"""
    buf = min(set(m)^set(l[a]+l[b]))
    l[a].append(buf)
    l[b].append(buf)
    """

    k=int(0)
    while True:
        if (k in l[a])==False:
            if (k in l[b])==False:
                l[a].append(k)
                l[b].append(k)
                break
            else:
                k +=1
        else:
            k +=1

    t.append(buf+1)
    #m.append(i+1)
print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[[] for j in range(n)]
m=[0]
t=[]

for i in range(n-1):
    a, b = map(int, input().split())
    a -=1
    b -=1
"""
    buf = min(set(m)^set(l[a]+l[b]))
    l[a].append(buf)
    l[b].append(buf)
    """
    k=int(0)
    while True:
        if (k in l[a])==False:
            if (k in l[b])==False:
                l[a].append(k)
                l[b].append(k)
                break
            else:
                k +=1
        else:
            k +=1

    t.append(buf+1)
    #m.append(i+1)
print(max(t))
for g in range(n-1):
    print(t[g])

Submission status: Runtime Error

Solution code:
n=int(input())
l=[]
w=[]
r2=[]
r1=[]
r3=[]
e=[]
t=int(1)
for i in range(n-1):
    a, b = map((int, input().split()))
    if a ==1:
        w.append([a,b])
        r2.appemd([i,t])
        t +=1

    else:
        l.append([a,b])
        r1.append([i,0])
def cal(l,w,c):
    while True:
        if l==[]:
            return r2,c
        t=1
        i=0
        while True:
            if (w[0][0] in l[i])==True or (w[0][1] in l[i])==True:
                w.insert(1,l[i])
                l.pop(i)
                r2.append(r2[0])
                if not r2[0][1]==t:
                    r1[0][1]=t
                else:
                    t +=1
                    r1[0][1]=t
                c=max(c,t)
                r2.insert(1,r1[0])
                r1.pop(0)
                r2.pop(0)
                t +=1
            else:
                i +=1

            if len[l]==i:
                i=0
                w.pop(0)

r3,c=cal(l,w,0)
e=sorted(r3)
for k in range(n-1):

print(c)
for g in range(n-1):
    print(e[g][1])

Submission status: Runtime Error

Solution code:
n=int(input())

l=[]
w=[]
r2=[]
r1=[]
r3=[]
e=[]
t=int(1)
for i in range(n-1):
    a, b = map((int, input().split()))
    if a ==1:
        w.append([a,b])
        r2.appemd([i,t])
        t +=1

    else:
        l.append([a,b])
        r1.append([i,0])



def cal(l,w,c):
    while True:
        if l==[]:
            return r2,c
        t=1
        i=0
        while True:
            if (w[0][0] in l[i])==True or (w[0][1] in l[i])==True:
                w.insert(1,l[i])
                l.pop(i)
                r2.append(r2[0])
                if not r2[0][1]==t:
                    r1[0][1]=t
                else:
                    t +=1
                    r1[0][1]=t
                c=max(c,t)
                r2.insert(1,r1[0])
                r1.pop(0)
                r2.pop(0)
                t +=1
            else:
                i +=1

            if len[l]==i:
                i=0
                w.pop(0)

r3,c=def(l,w,0)
e=sorted(r3)
for k in range(n-1):

print(c)
for g in range(n-1):
    print(e[g][1])

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
hen = collections.deque()
for _ in range(n):
	a,b = map(int,input().split())
	hen.append([a,b])
cht = dict()
for x,y in hen:
	try:
		cht[x] += 1
	except KeyError:
		cht[x] = 1
	try:
		cht[y] += 1
	except KeyError:
		cht[y] = 1
	
print(max(cht.values()))

Submission status: Runtime Error

Solution code:
N= int(input())

G = [[]*N for i in range(N)]

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

ans = [0]*(N-1)

def func(prt, col):
    cnt = 1
    for cld, org in G[prt]:
        if cnt==org:
            cnt += 1
        ans[org] = cnt
        func(cld, cnt)
        cnt += 1

func(0, 0)

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

Submission status: Runtime Error

Solution code:
n=int(input())
E=[[] for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    E[a].append([b,i])
    E[b].append([a,i])
k=0
for e in E:
    k=max(k,len(e))
ans=[0]*(n-1)
def dsf(v,p,vp_c):
    c=1
    for u,i in E[v]:
        if u!=p:
            if c==vp_c:
                c+=1
            ans[i]=c
            dsf(u,v,c)
            c+=1
dsf(1,0,0)
print(k)
for i in range(n-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
read = sys.stdin.read

def main():
    N, *ab = map(int, read().split())
    E = [[] for _ in range(N + 1)]
    
    for a, b in zip(*[iter(ab)] * 2):
        E[a].append(b)
        edge_order.append(b)
    
    # 頂点1から幅優先探索
    queue = deque([1])
    color = [0] * (N+1) 
    while queue:
        V = queue.popleft()
        c = 1
        for i in E[V]:
            if c == color[V]:
                c += 1
            color[i] = c
            c += 1
            queue.append(i)

    print(max(color))
    for i in edge_order:
        print(color[i])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline


class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.edge_color = []


def dfs(node, p):
    # print(node.num, p)
    for e in node.edge:
        used_color = node.edge_color
        if e != p:
            # 子のノードを取得
            child = tree[e]
            child_used_color = child.edge_color

            # このnodeと子のノードでまだ使っていない色を特定
            unused_colors = list(set(colors) - set(used_color + child_used_color))
            if len(unused_colors) == 0:
                color_num = max(colors) + 1
                colors.append(color_num)
            else:
                color_num = unused_colors[0]

            # このノードと、子のノードに使用ずみの色をマーク
            node.edge_color.append(color_num)
            child.edge_color.append(color_num)

            # 答えを記録
            ans['{a} {b}'.format(a=node.num, b=child.num)] = color_num
            ans['{a} {b}'.format(a=child.num, b=node.num)] = color_num

            # 掘る
            dfs(child, node.num)


N = int(input())
ans = {}
colors = [1]

# treeの初期化
tree = []
edges = []
tree.append(Node(0))
for i in range(1, N + 1):
    tree.append(Node(i))
for i in range(N - 1):
    inp = input().split()
    edges.append(inp)
    a, b = map(int, inp)
    tree[a].edge.append(b)
    tree[b].edge.append(a)

dfs(tree[1], -1)


print(len(colors))
for e in edges:
    # print(e)
    print(str(ans.get(' '.join(e))))

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
for idx, (a, b) in enumerate(ab):
    a, b = a-1, b-1
    edge[a].append([b, a, 0, idx])

next_list = []
now_list = [0]
colors = [0] * (N-1)
color_list = set()
now_color = 2
max_color = 0
while len(now_list) > 0:
    for v in now_list:
        for idx, nextv in enumerate(edge[v]):
            if v == nextv[0]:
                continue
            colors[nextv[0]] += 1
            edge[v][idx][2] = colors[nextv[0]]
            max_color = max(max_color, now_color-1)
            next_list.append(nextv[0])
    
    now_list = list(next_list)
    next_list = []

ret = []
for ed in edge:
    for e in ed:
        ret.append(e)
ret.sort(key=lambda  x:x[3])
print(max_color)
for ed in ret:
    print(ed[2])

Submission status: Runtime Error

Solution code:
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline


class Node:
    def __init__(self, num):
        self.num = num
        self.edge = []
        self.edge_color = []


def dfs(node, p):
    # print(node.num, p)
    for e in node.edge:
        used_color = node.edge_color
        if e != p:
            # 子のノードを取得
            child = tree[e]
            child_used_color = child.edge_color

            # このnodeと子のノードでまだ使っていない色を特定
            unused_colors = list(set(colors) - set(used_color + child_used_color))
            if len(unused_colors) == 0:
                color_num = max(colors) + 1
                colors.append(color_num)
            else:
                color_num = unused_colors.pop()

            # このノードと、子のノードに使用ずみの色をマーク
            node.edge_color.append(color_num)
            child.edge_color.append(color_num)

            # 答えを記録
            ans['{a} {b}'.format(a=node.num, b=child.num)] = color_num

            # 掘る
            dfs(child, node.num)


N = int(input())
ans = {}
colors = [1]

# treeの初期化
tree = []
edges = []
tree.append(Node(0))
for i in range(1, N + 1):
    tree.append(Node(i))
for i in range(N - 1):
    inp = input().split()
    edges.append(inp)
    a, b = map(int, inp)
    tree[a].edge.append(b)
    tree[b].edge.append(a)


dfs(tree[1], -1)


print(len(colors))
for e in edges:
    # print(e)
    print(str(ans.get(' '.join(e))))

Submission status: Runtime Error

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

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for u, ei in g[v]:
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
# print(g)

ans = [0] * (N-1)

def dfs(v, c=-1, p=-1):
    global g, ans
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)

dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
edge = [[] for _ in range(N)]
for a, b in ab:
    a, b = a-1, b-1
    edge[a].append(b)

next_list = []
now_list = [0]
colors = [0] * N
colors[0] = 1
color_list = set()
now_color = 2
while len(now_list) > 0:
    if not 1 in color_list:
        now_color = 1
    color_list = set()
    for v in now_list:
        for nextv in edge[v]:
            if v == nextv:
                continue
            colors[nextv] = now_color
            color_list.add(now_color)
            now_color += 1
            next_list.append(nextv)
    
    now_list = list(next_list)
    next_list = []
            
print('\n'.join(colors))

Submission status: Runtime Error

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

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def make_set(v1, v2):
    return (min(v1, v2), max(v1, v2))

N = int(input())
edges = defaultdict(list)
edge_list = []
for n in range(N - 1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
    edge_list.append(make_set(a, b))

edge_to_color = {}
def color_edges(prev, curr, prev_color):

    used_set = set([prev_color])
    next_color = 1

    for nei in edges[curr]:
        if nei == prev:
            continue
        while True:
            if next_color in used_set:
                next_color += 1
            else:
                break
        used_set.add(next_color)
        edge_to_color[make_set(curr, nei)] = next_color
        color_edges(curr, nei, next_color)

color_edges(-1, 1, -1)
K = max(len(x) for x in edges.values())
print(K)
for edge in edge_list:
    print(edge_to_color[edge])

Submission status: Runtime Error

Solution code:
import math
import sys

UNDEF=-1
sys.setrecursionlimit(1000010)
N = int(input())
# print(N)
V=[[UNDEF,UNDEF,[],[] ] for _ in range(N) ]      # Vertex
E=[[] for _ in range(N-1) ]    # Edge 

for i in range(N-1):
    (xa,xb) = map(int,input().split())
    # print(xa,xb)
    E[i]=[xa,xb]
    V[xb-1][0]=xa
    V[xb-1][1]=i+1
    V[xa-1][2].append(xb)
    V[xa-1][3].append(i+1)


# print("Edge:", E)
# print("Vertex:",V)

def root_v():
    global UNDEF
    global V
    for i in range(len(V)):
        if V[i][0] == UNDEF:
            return i+1
    return UNDEF

# print("Root Node:",root_v())

def max_degree(s):
    if V[s-1][0] != UNDEF: 
        degree=len(V[s-1][2]) + 1 # Node S 's degree for non root
    else:
        degree=len(V[s-1][2])     # Node S 's degree for root 

    for c in V[s-1][2]:
        degree = max ( degree, max_degree(c) ) 
    return degree

# print("Max Degree:", max_degree(root_v()))
print(max_degree(root_v()))

# Initialize 'color list' for edges
color=[UNDEF for _ in range(N-1)]

def put_colors(s):
    # print("put_color",s)
    global color 
    pcolor = color[V[s-1][1]-1]
    ic = 1
    for i in range(len(V[s-1][3])):
        if ic == pcolor:
            ic = ic + 1
        # print("put_color",s,i,V[s-1][3][i], ic )
        color[V[s-1][3][i]-1] = ic 
        put_colors(V[s-1][2][i])
        ic = ic + 1
    
put_colors(root_v())
for i in range(N-1):
    print(color[i])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

# def main():
#     N = int(input())
#     sides = [[] for _ in range(N-1)]
    
#     for i in range(N-1):
#         a,b = map(int, input().split())
#         sides[a-1].append((b-1,i))

#     ans = [[None] for _ in range(N-1)]

#     def dfs(focus,parent_color):
#         color = 1
#         for child,index in sides[focus]:
#             if parent_color == color:
#                 color += 1 #もし親の色と被っていた場合はその色を飛ばす
#             ans[index] = color
#             if child < N-1:
#                 dfs(child,color)
#             color += 1 #同じ親から続く次の辺の色を変更する

#     dfs(0,0)

#     print(max(ans))
#     for color in ans:
#         print(color)

def main():
    N = int(input())

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

    ans = [[None] for _ in range(N-1)]

    def dfs(v0, c0):
        c = 1
        for v1, e in g[v0]:
            if c==c0:
                c += 1
            ans[e] = c
            if v1 < N-1:
                dfs(v1, c)
            c += 1

    dfs(0, 0)

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import copy

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

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            if child < N-1:
                dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import copy

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

    ans = [[None] for _ in range(N-1)]

    def dfs(focus,parent_color):
        # if focus == N - 1:
        #     return
        color = 1
        for child,index in sides[focus]:
            if parent_color == color:
                color += 1 #もし親の色と被っていた場合はその色を飛ばす
            ans[index] = color
            if child < N -1:
                dfs(child,color)
            color += 1 #同じ親から続く次の辺の色を変更する

    dfs(0,0)

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

if __name__ == "__main__":
    main()