CEDGE
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một cây (đồ thi liên thông vô hướng không chu trình) gồm \(N\) nút. Các nút được đánh số từ 1 đến \(N\).
Nhiệm vụ của bạn là tô màu các cạnh trên cây, sao cho với mỗi nút, không có hai cạnh bất kì kề với nút đó được tô cùng một màu. Trong các cách tô màu thỏa mãn, hãy tìm cách tô dùng ít màu phân biệt nhất.
Lưu ý: Nếu có nhiều cách tô dùng ít màu phân biệt nhất và thỏa mãn điều kiện, bạn có thể in ra một cách bất kì.
Input
- Dòng đầu tiên gồm một số nguyên \(N (2<N<10^5)\).
- \(N—1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) \((1<a_i,b_i<N)\) biểu diễn cạnh nối giữa nút \(a_i\) và \(b_i\).
Output
- Dòng đầu tiên in ra một số nguyên \(K\) là số lượng màu phân biệt ít nhất được dùng để tô.
- \(N—1\) dòng tiếp theo, dòng thứ \(i\) in ra một số nguyên \(c_i\) \((1<c_i<K)\) biểu diễn màu của cạnh thứ \(i\) trong cách cho ban đầu.
Example
Test 1
Input
3
1 2
2 3 Output
2
1
2Test 2
Input
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8 Output
4
1
2
3
4
1
1
2Test 3
Input
6
1 2
1 3
1 4
1 5
1 6 Output
5
1
2
3
4
5
Bình luận
Bài này hình như test lỗi thì phải thấy in cái j cũng ac
-
0
jumptozero
8:07 a.m. 31 Tháng 5, 2021
-
0
tuanha2
8:30 a.m. 31 Tháng 5, 2021
-
1
jumptozero
9:25 a.m. 31 Tháng 5, 2021
1 bình luận nữaBạn có thể nói rõ là in cái gì được không bạn, vì mình thấy test cũng ổn á, bạn có thể gửi link ideone vào đây nhé !
Anh xem code em đi em in hello cũng ac
Ừ nhỉ, cảm ơn bạn, mình đã báo cáo để BQT xem xét rồi nhé!