Xây lại đường

Có $n$ thành phố và đúng $n-1$ con đường hai chiều nối giữa chúng. Do đường sá được xây dựng không có quy hoạch, mạng lưới hiện tại có thể không liên thông (không phải từ thành phố nào cũng đi được tới mọi thành phố khác) và có thể chứa chu trình.

Chính quyền muốn cải tạo lại sao cho từ mỗi thành phố đều có thể đi tới tất cả các thành phố còn lại. Mỗi ngày họ có thể thực hiện một thao tác: đóng một con đường đang tồn tại và ngay lập tức xây một con đường mới nối hai thành phố bất kỳ (con đường mới phải nối hai thành phố khác nhau).

Hãy xác định số ngày ít nhất cần thiết để mạng lưới trở nên liên thông, đồng thời đưa ra kế hoạch đóng đường cũ và xây đường mới.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, số thành phố.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a_i$, $b_i$ mô tả một con đường nối thành phố $a_i$ và $b_i$.

Giữa một cặp thành phố có không quá một con đường, và không có con đường nào nối một thành phố với chính nó.

Dữ liệu ra

• Dòng đầu ghi số nguyên $t$, số ngày ít nhất cần thiết.
• $t$ dòng tiếp theo, mỗi dòng mô tả một ngày dưới dạng $ijuv$: đóng con đường giữa hai thành phố $i$ và $j$ (con đường này phải đang tồn tại tại thời điểm đó) và xây con đường mới giữa hai thành phố $u$ và $v$.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $2\le n\le 1000$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$

Ví dụ