CSES - Network Renovation | Đổi mới mạng lưới
Xem PDF
Điểm:
2000 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Mạng lưới của Syrjälä gồm \(n\) máy tính và \(n − 1\) kết nối giữa chúng. Có thể gửi dữ liệu giữa hai máy tính bất kỳ.
Tuy nhiên, nếu bất kỳ kết nối nào bị hỏng, sẽ không còn có thể gửi dữ liệu giữa một số máy tính. Nhiệm vụ của bạn là thêm số lượng kết nối mới tối thiểu theo cách mà bạn vẫn có thể gửi dữ liệu giữa hai máy tính bất kỳ ngay cả khi bất kỳ kết nối đơn lẻ nào bị hỏng.
Input
- Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng máy tính. Các máy tính được đánh số \(1, 2,\ldots, n\).
- Sau này, có \(n - 1\) dòng mô tả các kết nối. Mỗi dòng có hai số nguyên \(a\) và \(b\): có kết nối giữa các máy tính \(a\) và \(b\).
Output
- Đầu tiên in một số nguyên \(k\): số lượng kết nối mới tối thiểu. Sau này, in \(k\) dòng biểu thị cho các kết nối. Bạn có thể in bất kỳ giải pháp nào hợp lệ.
Constraints
- \(3 \le n \le 10^5\)
- \(1 \le a, b \le n\)
Example
Sample input
5
1 2
1 3
3 4
3 5
Sample output
2
2 4
4 5
Bình luận
CSES - Network Renovation | Đổi mới mạng lưới
Mạng lưới của Syrjälä gồm \(n\) máy tính và \(n-1\) kết nối giữa chúng. Mạng lưới đảm bảo có thể gửi dữ liệu giữa hai máy tính bất kì.
Tuy nhiên, nếu một kết nối bất kì bị hỏng, một số máy tính sẽ không thể gửi dữ liệu được cho nhau. Nhiệm vụ của bạn là thêm vào số kết nối tối thiểu sao cho hai máy tính bất kì có thể gửi dữ liệu cho nhau ngay cả khi có một kết nối nào đó bị hỏng.
Input
Output
Test 1
Input
Output