CSES - Network Renovation | Đổi mới mạng lưới

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
kitsune
Dạng bài
Đ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


  • 0
    nguyen_ducminh    12:44 a.m. 2 Tháng 9, 2023

    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

    • Dòng đầu tiên gồm số nguyên \(n\) (\(3 \leq n \leq 10^5\)) - số lượng máy tính. Các máy tính được đánh chỉ số \(1, 2, ..., n\).
    • \(n-1\) dòng tiếp theo mô tả các kết nối. Mỗi dòng gồm hai số nguyên \(a\) và \(b\) (\(1 \leq a,b \leq n\)) với ý nghĩa có kết nối giữa hai máy \(a\) và \(b\).

    Output

    • Đầu tiên in ra \(k\) - số lượng kết nối mới tối thiểu. Sau đó, in ra \(k\) dòng mô tả các kết nối. Bạn có thể in ra một phương án hợp lệ bất kì.

    Test 1

    Input 
    5
1 2
1 3
3 4
3 5
    Output 
    2
2 4
4 5
      • 1 bình luận nữa