Andryusha và những quả bóng màu

Thời gian một lần thử: 2 giây

Dung lượng bộ nhớ mỗi lần thử: 256 megabytes

Input: đầu vào chuẩn (nhập từ bàn phím)

Output: đầu ra chuẩn (hiển thị màn hình)

Mỗi ngày Adryusha đều đi qua một công viên nọ. Cảnh vật với những lối mòn làm ông phát chán, vì vậy ông đã quyết định “làm đẹp” nó.

Công viên gồm n ô vuồng với (n-1) lối (mỗi lối có hai hướng) sao cho từ 1 ô bất kì cũng có thể đến 1 ô bất kì trong các ô còn lại qua các lối này.

Adryusha quyết định treo những quả bóng nhiều màu lên mỗi ô vuông. Màu của các quả bóng được biểu diễn bởi số nguyên dương bắt đầu từ 1. Để làm công viên trông thật rực rỡ, Andryusha muốn chọn màu theo một cách đặc biệt. cẩn thận hơn, ông muôn dùng những màu sắc mà nếu a,b và c là những hình vuông khác biệt a,b có đường đi nối trực tiếp, b và c có đường đi nối trực tiếp với nhau thì màu của các quả bóng trên ba ô này sẽ khác nhau đôi một.

Andryusha muốn sử dụng ít màu khác nhau nhất có thể, bạn hãy giúp ông ấy!

Input

  • Dòng đầu gồm một số nguyên duy nhất n (3<=n<=2*10^5)- số ô vuông của công viên
  •  n-1 dòng tiếp theo gồm 2 số nguyên x và y (1<=x,y<=n)- là chỉ số của hai ô nối trực tiếp bởi một lối đi
  • Phải đảm bảo rằng mỗi một ô đều có thể đến đươc từ bất kì ô nào khác bằng các lối đi

Output

  • Dòng đầu tiên: số nguyên  k – số lượng tối thiểu của màu sắc Andryusha phải sử dụng
  • Dòng thứ hai: n số nguyên a, mỗi số nguyên lần lượt là số thứ tự của màu quả bóng trên mỗi ô vuông tương ứng (1<=a<=k). Ở ví dụ 3 bên dưới cần dùng tối thiểu 3 màu,ta đánh số tương ứng các màu là 1,2,3. Các ô vuông từ 1->5 sẽ được ghi tương ứng với màu quả bóng đã được đánh số.

 

vd1:

Input

Output

vd2:

Input

Output

vd3:

Input

Output

Gợi ý:

Trong ví dụ đầu tiên, công viên bao gồm ba ô vuông: 1 → 3 → 2. Vì vậy, màu bóng cần phải khác biệt.

Ví dụ  thứ hai ,các ô vuông được kết nối như sau:

  • 1 → 3 → 2
  • 1 → 3 → 4
  • 1 → 3 → 5
  • 2 → 3 → 4
  • 2 → 3 → 5
  • 4 → 3 → 5

 

Ta thấy rằng các ô vuông khác đều chỉ kết nối trực tiếp với ô số 3 nên các ô phải có màu khác nhau.

Vi dụ 3 các ô vuông được kết nối:

  • 1 → 2 → 3
  • 2 → 3 → 4
  • 3 → 4 → 5

1 hoặc 2 màu là không đủ,nhưng ta có thể khẳng định rằng ta chỉ cần sử dụng 3 màu.

Nguồn: http://codeforces.com/contest/782/problem/C

Người Dịch: Nguyễn Chí Trung 

The following two tabs change content below.

vuminhtu