Submission #8613631


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = list(zip(m,m))

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1

answer = []
append = answer.append
for a,b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])

K = max(answer)
print(K)
print('\n'.join(map(str,answer)))

Submission Info

Submission Time
Task D - Coloring Edges on Tree
User maspy
Language Python (3.4.3)
Score 400
Code Size 961 Byte
Status AC
Exec Time 381 ms
Memory 38292 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 26
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 11-small-01.txt, 11-small-02.txt, 11-small-03.txt, 11-small-04.txt, 11-small-05.txt, 11-small-06.txt, 11-small-07.txt, 11-small-08.txt, 11-small-09.txt, 11-small-10.txt, 31-large-01.txt, 31-large-02.txt, 31-large-03.txt, 31-large-04.txt, 31-large-05.txt, 41-min-01.txt, 51-max-01.txt, 61-path-01.txt, 61-path-02.txt, 61-path-03.txt, 71-star-01.txt, 71-star-02.txt, 71-star-03.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 17 ms 3064 KB
00-sample-02.txt AC 17 ms 3064 KB
00-sample-03.txt AC 17 ms 3064 KB
11-small-01.txt AC 17 ms 3064 KB
11-small-02.txt AC 18 ms 3064 KB
11-small-03.txt AC 18 ms 3064 KB
11-small-04.txt AC 19 ms 3188 KB
11-small-05.txt AC 18 ms 3064 KB
11-small-06.txt AC 18 ms 3188 KB
11-small-07.txt AC 18 ms 3064 KB
11-small-08.txt AC 18 ms 3064 KB
11-small-09.txt AC 19 ms 3188 KB
11-small-10.txt AC 18 ms 3064 KB
31-large-01.txt AC 46 ms 6504 KB
31-large-02.txt AC 223 ms 24692 KB
31-large-03.txt AC 82 ms 10836 KB
31-large-04.txt AC 77 ms 9908 KB
31-large-05.txt AC 173 ms 19156 KB
41-min-01.txt AC 17 ms 3064 KB
51-max-01.txt AC 381 ms 38292 KB
61-path-01.txt AC 199 ms 23352 KB
61-path-02.txt AC 60 ms 8136 KB
61-path-03.txt AC 67 ms 9192 KB
71-star-01.txt AC 51 ms 7256 KB
71-star-02.txt AC 238 ms 28248 KB
71-star-03.txt AC 105 ms 13448 KB