Lara rất thích các khu chợ trời. Thứ Bảy vừa qua, tại Bonn diễn ra chợ Rheinaue-Flohmarkt, một trong những khu chợ trời lớn nhất nước Đức. Tất nhiên, Lara đã dành cả ngày ở đó, dạo quanh chợ, mặc cả và mua đủ loại đồ vật lạ mắt. Món đồ thú vị nhất cô mang về nhà là một cây đàn hạc nhỏ có dạng hình tròn hoàn hảo. Khi muốn bắt đầu chơi đàn, cô nhận thấy các dây đàn nằm lộn xộn thay vì song song với nhau.

Cụ thể hơn, có ~2 \cdot N~ chốt được bố trí cách đều nhau quanh khung đàn hình tròn. Mỗi dây trong số ~N~ dây đàn được cố định bằng hai chốt, và mỗi chốt có đúng một dây đàn được gắn vào.

Lara không biết nhiều về đàn hạc, nhưng cô khá chắc rằng các dây đàn cần được sắp xếp sao cho chúng song song với nhau. Để khắc phục vấn đề này, cô quyết định mắc lại dây cho cây đàn. Trong mỗi bước, cô có thể tháo một đầu dây đàn khỏi chốt đang giữ nó và gắn lại vào một chốt khác. Trong quá trình này, các đầu của nhiều dây đàn có thể cùng được gắn vào một chốt. Cuối cùng, mỗi chốt phải lại có đúng một dây đàn được gắn vào, và ~N~ dây đàn phải song song với nhau.

Vì mỗi bước mắc lại dây đều tốn nhiều công sức, Lara muốn mắc lại dây đàn với ít bước nhất có thể. Hãy giúp Lara tìm một trình tự mắc lại dây đàn với số bước nhỏ nhất!

Input

Dòng đầu tiên của dữ liệu vào chứa một số nguyên ~N~, cho biết số dây đàn. Các dây đàn được đánh số từ ~0~ đến ~N-1~.

Tiếp theo là ~N~ dòng, trong đó dòng thứ ~i~ (~0 \le i \le N-1~) chứa hai số nguyên ~a_i~ và ~b_i~, là hai chốt giữ dây đàn thứ ~i~. Các chốt được đánh số theo chiều kim đồng hồ từ ~0~ đến ~2 \cdot N-1~. Mỗi chốt có đúng một dây đàn được gắn vào.

Output

In ra một số nguyên ~K~, là số bước nhỏ nhất cần thực hiện để mắc lại dây cho cây đàn sao cho tất cả các dây đàn song song với nhau.

Tiếp theo, in ra ~K~ dòng, mỗi dòng chứa ba số nguyên ~p~, ~s~ và ~e~, cho biết trong bước này của phương án, một đầu của dây đàn thứ ~p~ được tháo khỏi chốt ~s~ và gắn lại vào chốt ~e~ (~0 \le p \le N-1~, ~0 \le s,e \le 2 \cdot N-1~).

Lưu ý rằng nếu tại thời điểm đó dây đàn thứ ~p~ không được gắn vào chốt ~s~, thì trình tự thao tác được coi là không đúng.

Nếu có nhiều đáp án, bạn có thể in ra một đáp án bất kỳ. Lưu ý rằng các đáp án đúng một phần vẫn có thể nhận được một số điểm, như được giải thích trong phần tiếp theo.

Scoring

• ~4 \le N \le 100000~.

• ~0 \le a_i,b_i \le 2 \cdot N-1~.

• Tất cả các giá trị ~a_i~ và ~b_i~ đôi một phân biệt.

Lời giải của bạn sẽ được kiểm tra trên một số nhóm test, mỗi nhóm có một số điểm nhất định. Mỗi nhóm test chứa một tập hợp các test. Với mỗi nhóm test, điểm số của bạn được xác định như sau:

• Nếu chương trình của bạn giải đúng tất cả các test trong nhóm, bạn nhận được ~100\%~ số điểm của nhóm.

• Nếu chương trình của bạn chưa giải hoàn toàn nhóm test nhưng in đúng số bước nhỏ nhất cho từng test trong nhóm, bạn nhận được ~50\%~ số điểm của nhóm.

Khi xác định liệu lời giải của bạn có nhận được ~50\%~ số điểm của một nhóm test hay không, chỉ giá trị ~K~ mà chương trình in ra được chấm. Lời giải có thể chỉ in ra giá trị ~K~ rồi kết thúc, hoặc thậm chí in ra một trình tự thao tác không hợp lệ. Lưu ý rằng lời giải của bạn vẫn phải hoàn thành trong giới hạn thời gian và kết thúc đúng cách.

Subtask	Điểm	Ràng buộc
1	~14~	Dây đàn thứ ~i~ được gắn vào các chốt ~2 \cdot i~ và ~2 \cdot i+1~ với mọi ~i~
2	~16~	Số bước cần thực hiện không quá ~2~
3	~12~	Bảo đảm tồn tại một phương án trong đó có một dây đàn được gắn vào các chốt ~0~ và ~1~
4	~28~	~N \le 1000~
5	~30~	Không có giới hạn gì thêm

Sample Input 1

5
1 5
4 9
6 3
2 7
0 8

Sample Output 1

3
4 8 9
0 5 8
1 9 5

Sample Input 2

5
0 1
3 2
4 5
6 7
9 8

Sample Output 2

4
1 3 9
4 9 3
2 5 7
3 7 5

Sample Input 3

4
1 4
6 3
5 2
7 0

Sample Output 3

2
0 4 6
1 6 4

Sample Input 4

6
3 9
7 5
10 2
0 6
1 11
8 4

Sample Output 4

6
3 6 1
4 1 2
2 2 3
0 3 4
5 4 5
1 5 6

Notes

Trong ví dụ thứ nhất, ta được cho một cây đàn hạc có năm dây. Ở bước đầu tiên, dây đàn ~4~ được tháo khỏi chốt ~8~ và gắn lại vào chốt ~9~. Ở bước tiếp theo, dây đàn ~0~ được tháo khỏi chốt ~5~ và gắn lại vào chốt ~8~. Ở bước cuối cùng, dây đàn ~1~ được tháo khỏi chốt ~9~ và gắn lại vào chốt ~5~. Lúc này, mỗi chốt có đúng một dây đàn được gắn vào và tất cả các dây đàn đều song song với nhau.

• Ví dụ thứ nhất thỏa mãn ràng buộc của các nhóm test ~4~ và ~5~.

• Ví dụ thứ hai thỏa mãn ràng buộc của các nhóm test ~1~, ~3~, ~4~ và ~5~.

• Ví dụ thứ ba thỏa mãn ràng buộc của các nhóm test ~2~, ~4~ và ~5~.

• Ví dụ thứ tư thỏa mãn ràng buộc của các nhóm test ~3~, ~4~ và ~5~.

Ghi công và giấy phép

Bài toán này có nguồn gốc từ EGOI 2025 (Olympic Tin học nữ châu Âu), Ngày 2, được tổ chức tại Bonn, Đức.

• Đề bài gốc: A String Problem

• Tác giả: Yoav Linhart.

• Chủ sở hữu bản quyền: Olympic Tin học nữ châu Âu 2025.

• Tài liệu chính thức: Đề bài và lời giải · Dữ liệu kiểm thử, trình chấm và các bản dịch

• Giấy phép: Creative Commons Ghi công – Chia sẻ tương tự (CC BY-SA), theo siêu dữ liệu chính thức của bài toán. Siêu dữ liệu không chỉ rõ phiên bản giấy phép.

• Các thay đổi: Dịch sang tiếng Việt và định dạng lại cho ClueOJ.

Bản dịch này được phân phối theo cùng các điều khoản CC BY-SA áp dụng cho bài toán gốc.

ClueOJ không có quan hệ liên kết với EGOI hoặc ban tổ chức EGOI 2025, cũng không được các bên này chứng thực.