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:
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

# n = 9
# arr = [
#     [1,2],
#     [1,6],
#     [2,8],
#     [2,3],
#     [2,7],
#     [3,9],
#     [3,4],
#     [4,5],
# ]

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [[] for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            nodeLines[currentNode].append(kk)
            dfs(childNodeIndex, arr, kk)



data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in nodeLines:
    for a in ar:
        print(a)

Submission status: Runtime Error

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

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [[] for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            nodeLines[currentNode].append(kk)
            dfs(childNodeIndex, arr, kk)




data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in nodeLines:
    for r in ar:
        print(r)

Submission status: Runtime Error

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

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
mm = []


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            mm.append(kk)
            dfs(childNodeIndex, arr, kk)




data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for m in mm:
    print(m)

Submission status: Runtime Error

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


childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [0 for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            appendIntoNode(currentNode+1,childNodeIndex+1,kk)
            dfs(childNodeIndex, arr, kk)


def appendIntoNode(currentNode,childNode,value):
    for i,v in enumerate(arr):
        if (v[0] == currentNode and v[1] == childNode):
            nodeLines[i] = value


data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in nodeLines:
    print(ar)

Submission status: Runtime Error

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

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [0 for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            appendIntoNode(currentNode+1,childNodeIndex+1,kk)
            dfs(childNodeIndex, arr, kk)


def appendIntoNode(currentNode,childNode,value):
    for i,v in enumerate(arr):
        if (v[0] == currentNode and v[1] == childNode):
            nodeLines[i] = value


data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in nodeLines:
    print(ar)

Submission status: Runtime Error

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  

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


class Edge():
    def __init__(self, to_, id_):
        self._to = to_
        self._id = id_


G = [[Edge]]
ans = []


def dfs(v, color, parent=-1):
    global G
    global ans
    c = 1
    if c == color:
        c += 1
    for g in G[v]:
        if g._to == parent:
            continue
        if ans[g._id] != -1:
            continue
        ans[g._id] = c
        dfs(g._to, c, v)
        c += 1
        if c == color:
            c += 1
    return


def main():
    # sys.stdin = open("sample.txt")
    global G
    global ans
    N = Scanner.int()
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        G[a].append(Edge(b, i))
        G[b].append(Edge(a, i))
    ans = [-1 for _ in range(N-1)]
    dfs(0, 0)
    print(max(ans))
    print(*ans, sep="\n")
    return


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
links = [[] for _ in range(n)]
colors = [0] * (n - 1)

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

def dfs(a, color):
    c = 1
    for b, i in links[a]:
        if c == color:
            c += 1
        colors[i] = c
        dfs(b, c)
        c += 1


dfs(0, 0)
print(max(colors))
for color in colors:
    print(color)

Submission status: Runtime Error

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

for itr, (a, b) in enumerate(AB):
  e[a].append((b, itr))
  e[b].append((a, itr))
  
cidx = max([len(i) for i in e])

ans = [-1] * (n - 1)

def dfs(v = 0, p = 0, p_col = -1):
  # 色は１から順に塗っていく
  col = 1
  for u, i in e[v]:
    if u != p:
      # 親と色がかぶる時は＋１
      if col == p_col:
        col += 1
      if ans[i] == -1: 
        ans[i] = col
      dfs(u, v, col)
      col += 1 

dfs()

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

Submission status: Runtime Error

Solution code:
n = int(input())
edge = [tuple(int(i) for i in input().split()) for i in range(n-1)]
to = [[] for _ in range(n+1)]
for e in edge:
    a,b = e
    to[a].append(b)
    to[b].append(a)
color = {}

def f(cn,pn,pc):
    c = 1
    for nn in to[cn]:
        if nn == pn: continue
        if c == pc: c += 1
        tmp = (cn,nn)
        color[(min(tmp),max(tmp))] = c
        f(nn,cn,c)
        c += 1

f(1,0,0)
print(max(color.values()))
for key in edge: print(color[key])

Submission status: Runtime Error

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

n = int(input())
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: Runtime Error

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]))
		if(l>max_color):
			max_color = l
		ch=[False]*max_color
		for j in e_colors[a]:
			ch[j-1]=True
		for j in e_colors[b]:
			ch[j-1]=True
		for j in range(l):
			if(ch[j]==False):
				e_colors[a].append(j+1)
				e_colors[b].append(j+1)
				ans_colors.append(j+1)
				break
	print(l)
	for i in range(N-1):
		print(ans_colors[i])

main()

Submission status: Runtime Error

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

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLineColors = [[] for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            nodeLineColors[currentNode].append(kk)
            dfs(childNodeIndex, arr, kk)


data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))


for ar in nodeLineColors:
    for a in ar:
        print(a)

Submission status: Runtime Error

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

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLineColors = [[] for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):
        if x == i:
            kk = kk + 1
        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            nodeLineColors[currentNode].append(kk)
            dfs(childNodeIndex, arr, i)


data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))
for ar in nodeLineColors:
    for a in ar:
        print(a)

Submission status: Runtime Error

Solution code:
x=int(input())
p=0
w=0
d=dict()
lol0=[]
for _ in range(x-1):
    a,b=map(int,input().split())
    d.setdefault(a,[]).append(b)
    d.setdefault(b,[]).append(a)
    lol0.append((a,b))
    c=max(len(d[a]),len(d[b]))
    if c>p:
        if len(d[a])>len(d[b]):
            p=len(d[a])
            w=a
        else: 
            p=len(d[b])
            w=b
q=[w]
m=dict()
v=[p-1]
vis=[1]*100001
vis[w]=0
yo=[*range(1,p+1)]
while len(q)>0:
    lol=q.pop(0)
    k=v.pop(0)
    for i in d[lol]:
        if vis[i]:
            m[(lol,i)]=yo[k]
            m[(i,lol)]=yo[k]
            vis[i]=0
            q.append(i)
            k-=1
            v.append(k)
print(p)
for i in lol0:
    print(m[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
d=defaultdict(list)
x=int(input())
p=0
w=0
lol0=[]
for _ in range(x-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    lol0.append((a,b))
    c=max(len(d[a]),len(d[b]))
    if c>p:
        if len(d[a])>len(d[b]):
            p=len(d[a])
            w=a
        else: 
            p=len(d[b])
            w=b
q=[w]
m=defaultdict(int)
v=[p-1]
vis=[1]*100001
vis[w]=0
yo=[*range(1,p+1)]
while len(q)>0:
    lol=q.pop(0)
    k=v.pop(0)
    for i in d[lol]:
        if vis[i]:
            m[(lol,i)]=yo[k]
            m[(i,lol)]=yo[k]
            vis[i]=0
            q.append(i)
            k-=1
            v.append(k)
print(p)
for i in lol0:
    print(m[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
d=defaultdict(list)
x=int(input())
p=0
w=0
lol0=[]
for _ in range(x-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    lol0.append((a,b))
    c=max(len(d[a]),len(d[b]))
    if c>p:
        if len(d[a])>len(d[b]):
            p=len(d[a])
            w=a
        else: 
            p=len(d[b])
            w=b
q=deque([w])
m=defaultdict(int)
v=deque([p-1])
vis=[1]*100001
vis[w]=0
yo=[*range(1,p+1)]
while len(q)>0:
    lol=q.popleft()
    k=v.popleft()
    for i in d[lol]:
        if vis[i]:
            m[(lol,i)]=yo[k]
            m[(i,lol)]=yo[k]
            vis[i]=0
            q.append(i)
            k-=1
            v.append(k)
print(p)
for i in lol0:
    print(m[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, b = 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):
  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)
print(max(ans))
for i in range(n-1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(50000)

tree = {}
N = 0

def assign(assignment, u, prev_color):
    color = 1
    for v in tree[u]:
        if color == prev_color:
            color += 1
        assignment[u,v] = color
        assign(assignment, v, color)
        color += 1

def main():
    global tree, N
    N = int(input())
    tree = {i: [] for i in range(1,N+1)}
    edges = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        tree[a].append(b)
        edges.append((a, b))
    ans = {}
    assign(ans, 1, None)
    print(max(ans.values()))
    for edge in edges:
        print(ans[edge])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

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

to=[[] for _ in range(N)]
for i in range(N-1):
  a, b=ab[i][0]-1, ab[i][1]-1
  to[a].append([b, i])
  to[b].append([a, i])

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

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
S = [list(map(int, input().split()))+[i] for i in range(N-1)]
A=[None]*(N-1)
l=[[] for i in range(N+1)]
t=[0]*N
t[0]=1
for i in S:
    l[i[0]].append((i[1],i[2]))
    l[i[1]].append((i[0],i[2]))
def haba(o,c):
    p=1
    for i in l[o]:
        if t[i[0]-1]==0:
            if c==p:
                p+=1
            A[i[1]]=p
            t[i[0]-1]=1
            haba(i[0],p)
            p+=1
haba(1,0)
print(max(A))
print(*A,sep="\n")

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
sys.setrecursionlimit(n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
sys.setrecursionlimit(n)
graph = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    edge.append({a,b})
    graph[a].append(b)
    graph[b].append(a)
k = max(len(i) for i in graph)

ans = [0]*(n-1)
def DFS(cur, pre=-1, p_color=-1):
    color = 1
    for i in graph[cur]:
        if i==pre:
            continue
        if color==p_color:
            color += 1
        ans[edge.index({cur, i})] = color
        DFS(i, cur, color)
        color += 1
DFS(0)
print(k)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
C = [[i for i in range(1,K+1)] for j in range(N+1)]

for i in range(N-1):
    a,b = W[i]
    x = C[a].pop(0)
    C[b].remove(x)
    print(x)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
from heapq import heappush, heappop
import itertools


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())

PATH = []
#COLOR = [[None for _ in range(N+1)] for _ in range(N+1)]
COLOR = defaultdict(int)
PT = [[] for _ in range(N+1)]
cmax = 1
for i in range(N-1):
    a, b = map(int, input().split())
    PATH.append((a, b))
    PT[a].append(b)
    PT[b].append(a)

    la = len(PT[a])
    lb = len(PT[b])

    l = la if la > lb else lb
    if l > cmax:
        cmax = l


q = deque([(1, 0)])

while(q):
    a, ca = q.popleft()
    bs = PT[a]

    c = list(range(1, cmax+1))
    for b in bs:
        if b > a:
            na = a
            nb = b
        else:
            na = b
            nb = a

        if COLOR[(na, nb)] == 0:
            clr = c.pop()
            if clr == ca:
                clr = c.pop()

            COLOR[(na, nb)] = clr
            q.append((b, clr))

print(cmax)

clr = []
for a, b in PATH:
    clr.append(COLOR[(a, b)])

print("\n".join(clr))

Submission status: Runtime Error

Solution code:
port sys
sys.setrecursionlimit(10**9)
 
N = int(input())
edge = [[] for i in range(N)]
count = [0] * N
color = {}
egs = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    count[a] += 1
    count[b] += 1
    edge[a].append(b)
    edge[b].append(a)
    egs.append(tuple(sorted([a, b])))
 
 
ans = max(count)
c = 1
 
 
 
def dfs(idx, pr):
    c = 1
    col = color[pr]
    for i in edge[idx]:
        if i in pr:
            continue
        if c == col:
            c+=1
        x, y = sorted([i, idx])
        color[(x, y)] = c
        dfs(i, (x, y))
        c+=1
 
color[(-1, -1)] = 0
dfs(0, (-1, -1))
print(ans)
for tpl in egs:
    print(color[tpl])

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq
# 入力、初期化
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)


# visitedにノードの色を格納する
visited_edge = [[0] * N for _ in range(N)]


# bfsによる色付けを行う
def bfs(now_node):
    queue = deque([[tree[now_node], 0, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1


bfs(0)
ans = []
for a, b in input_list:
    ans.append(visited_edge[a][b])
max_val = 0
for row in visited_edge:
    row = row.sort()
    tmp_max = row[-1]
    if tmp_max > max_val:
        max_val = tmp_max
print(max_val)
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
from math import sqrt
from fractions import gcd 
A, B = map(int,input().split())
Y = gcd(A, B)
ans = 1
if Y != 1:
    for i in range(2, min(Y+1,int(sqrt(Y))+2)):
        tmp = 0
        if i > Y:
            break
        while True:
            if Y%i == 0:
                Y //= i
                tmp += 1
            else:
                if tmp > 0:
                    ans += 1
                break
    if ans == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    q.append(tuple(sorted([a,b])))
    
#print(d)
m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=0
    for i in d[point]:
        colar+=1
        if tuple(sorted([point,i])) not in dcolars:
            if c==colar:
                colar+=1
            dcolars[tuple(sorted([point,i]))]=colar
            dcolars[tuple(sorted([point,i])[::-1])]=colar
            BFS(d,i,colar)

    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import*
from copy import *
n=int(input())
d=defaultdict(list)

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    q.append(tuple(sorted([a,b])))
    
#print(d)
m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=0
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            if c==colar:
                colar+=1
            dcolars[tuple(sorted([point,i]))]=colar
            dcolars[tuple(sorted([point,i])[::-1])]=colar
            BFS(d,i,colar)
        colar+=1
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import*
from copy import *
n=int(input())
d=defaultdict(list)

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    q.append(tuple(sorted([a,b])))
    
#print(d)
m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=deque(range(1,m+1))
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            ckamo=colar.pop()
            if c==ckamo:
                csave=deepcopy(ckamo)
                ckamo=colar.pop()
                colar.append(csave)
            dcolars[tuple(sorted([point,i]))]=ckamo
            BFS(d,i,ckamo)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import*
from copy import *
n=int(input())
d=defaultdict(list)

q=[]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    q.append(tuple(sorted([a,b])))
    
#print(d)
m=max(map(len,d.values()))
print(m)

dcolars={}

def BFS(d,point,c):
    colar=set(range(1,m+1))
    for i in d[point]:
        if tuple(sorted([point,i])) not in dcolars:
            ckamo=colar.pop()
            if c==ckamo:
                csave=deepcopy(ckamo)
                ckamo=colar.pop()
                colar.add(csave)
            dcolars[tuple(sorted([point,i]))]=ckamo
            BFS(d,i,ckamo)
    return dcolars

ans=BFS(d,1,0)

for i in q:
    print(ans[i])

Submission status: Runtime Error

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

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

es = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es[a].append((b, i))
    es[b].append((a, i))


# BFS
colors = {}
root = 0 # 頂点1が存在することが問題文中で保証されてるからここを根ノードとしよう
root_child0, _ = es[root][0]
colors[(root,root_child0)] = 1
K = 0
queue = [root]
visited = [0]*n
visited[root] = 1

ans_color = [0]*(n-1)

while queue:
    v = queue.pop(0)
    visited[v] = 1

    color = 1
    parent, _ = es[v][0] # vがrootの時は変なことになるけど後で弾くから大丈夫
    color_parent = colors[(v, parent)]

    for to, j in es[v]:
        if visited[to]: continue
        queue.append(to)

        if color == color_parent and v != root:
            color += 1

        colors[(v,to)] = color
        colors[(to,v)] = color

        ans_color[j] = color

        K = max(K, color)
        color += 1


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

Submission status: Runtime Error

Solution code:
n = int(input())
bfs_dic = [{} for i in range(n)]
ans = [0 for i in range(n-1)]

def bfs(pn, pc, node):
    c = 1
    max_c = 0
    
    if len(bfs_dic[node]) != 1 or pc == 0: #葉は見ない(葉でも最初だけは子を見る)
        for k,v in bfs_dic[node].items():
            if k == pn: continue #親と同じなら無視
            if pc == c:                 #親と色被っちゃったら色変え
                c+=1
            ans[v] = c
            maxable_c = bfs(node, c, k)
            if max_c < maxable_c:
                max_c = maxable_c
            c+=1                        #子と自分の間に色割り当てて色変える
        if max_c < c-1:
            return c-1
        else:
            return max_c
    return 1                                        #葉やったら1色しか使っとらん
            
for i in range(n-1):
    a,b = map(int, input().split())
    a-=1
    b-=1
    bfs_dic[a][b] = i
    bfs_dic[b][a] = i

print(bfs(-1, 0, 0))
for i in ans:
    print(i)