Tái cấu trúc tuyến cáp

Bối cảnh và bài toán

Một mạng có n trạm và đúng n-1 tuyến cáp hai chiều. Do quá trình triển khai thiếu đồng bộ, toàn mạng có thể chưa liên thông: một số khu vực chứa chu trình thừa trong khi các khu vực khác vẫn bị tách rời.

Mỗi ngày, đội kỹ thuật được tháo đúng một tuyến cáp dư và dùng chính vật tư đó để nối hai component khác nhau. Một tuyến được coi là dư theo quy tắc sau: khi đọc các tuyến theo thứ tự input và chỉ giữ những tuyến nối hai component khác nhau, tuyến nào nối hai trạm vốn đã liên thông bởi các tuyến được giữ trước đó sẽ được đánh dấu dư.

Để việc chấm tự động có kết quả duy nhất, kế hoạch phải tuân theo quy tắc chuẩn hóa ở phần Yêu cầu.

Yêu cầu

Hãy đưa mạng về trạng thái liên thông với số ngày nhỏ nhất và in kế hoạch chuẩn hóa:

1. Xử lý các tuyến theo thứ tự input, lưu các tuyến dư theo đúng thứ tự xuất hiện.
2. Sau khi xử lý hết, với mỗi component lấy trạm có số nhỏ nhất làm đại diện; sắp các đại diện tăng dần thành r1 < r2 < ... < rk.
3. Có đúng k-1 tuyến dư. Với ngày i (1 <= i < k), tháo tuyến dư thứ i và xây tuyến mới nối r1 với r(i+1).

In số ngày và toàn bộ kế hoạch.

Input

• Dòng 1 chứa n.
• n-1 dòng tiếp theo, dòng thứ i chứa a_i b_i, mô tả tuyến cáp thứ i.

Output

• Dòng đầu in số ngày t.
• Mỗi trong t dòng tiếp theo in bốn số a b u v: tháo tuyến cáp cũ (a,b) và xây tuyến mới (u,v) theo đúng quy tắc chuẩn hóa.

Ràng buộc

• 2 <= n <= 2 * 10^5
• 1 <= a_i, b_i <= n, a_i != b_i
• Không có hai tuyến input trùng hoàn toàn cùng một cặp không thứ tự.

Chấm điểm

Ví dụ 1

Input

7
1 2
2 3
3 1
4 5
5 6
6 7

Output

1
3 1 1 4

Giải thích. Tuyến 3–1 là tuyến dư đầu tiên. Hai component có đại diện nhỏ nhất là 1 và 4, nên dùng tuyến dư đó để nối 1–4.

Ví dụ 2

Input

4
1 2
2 3
3 4

Output

0

Giải thích. Mạng đã liên thông và không có tuyến dư, nên không cần ngày tái cấu trúc nào.

Thông tin bài tập

Yêu cầu ngoài OJ: khuyến nghị học viên nộp thêm Decision Note giải thích vì sao số tuyến dư luôn bằng số component trừ 1.

Nguồn: Phỏng theo Codeforces Beta Round #25 – D: Roads not only in Berland.