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

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
2014-12-25 15:33:32 Duc M. Pham
Code bài này tròn 100 dòng @@
2014-07-10 05:45:38 KNEO
TH nhiều kết quả?
2013-10-31 16:15:37 Chuyên Triết Tổng Hợp
clq nhưng hôm nay là halloween
2013-05-26 16:47:33 ‡■■Lãng du■■‡
Quy hoạch động trên cây
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.