Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CTREE - Tô màu nhỏ nhất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/ctree


Cho một cây gồm N nút, hãy tìm cách gán mỗi đỉnh một nhãn nguyên dương sao cho:
+ Hai nút có cạnh nối được gán bởi hai nhãn khác nhau.
+ Tổng giá trị các nhãn là nhỏ nhất.

Input

Dòng đầu tiên ghi N ( 1 ≤ N ≤ 10000).
N-1 dòng tiếp theo, mỗi dòng ghi hai nút là hai đầu mút của một cạnh thuộc cây.

Output

Dòng đầu tiên ghi S là tổng giá trị nhãn tìm được.
N dòng tiếp theo, dòng thứ i ghi nhãn gán cho đỉnh i trong phép gán tối ưu tìm được.

Example

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

Output:
11
3
1
1
1
2
1
1
1


Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-26
Thời gian chạy:0.100s
Giới hạn mã nguồn:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Mr Tran Quang Khai

hide comments
2021-05-27 18:00:40
Tham khảo: https://vnspoj.github.io/problems/CTREE
2019-11-26 17:21:12
chắc là DFS 0 1 :V
2019-07-13 17:43:24
nghe don bai nay test yeu
2018-01-06 05:10:37
1 2
2018-01-06 03:06:36
BU1 TH4NH EAT SHIT
2017-12-27 09:42:34
1 đấm AC :>
frostpixel aka.How 2 AC
2017-12-06 09:03:03
nhật hào sạch
2017-07-17 18:29:45


Last edit: 2017-07-17 18:29:59
2017-07-17 18:29:44
code 40 dong 1 dam ac
2017-05-28 09:38:46
1 đấm hơi nhiều :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.