Dưới đường chéo chính

Cho một ma trận vuông gồm $n$ dòng và $n$ cột. Các dòng được đánh số từ $1$ đến $n$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $n$ từ trái sang phải.

Đúng $n-1$ ô của ma trận chứa số $1$, tất cả các ô còn lại chứa số $0$. Bạn được phép thực hiện hai loại thao tác:

1. Đổi chỗ dòng $i$ và dòng $j$ của ma trận;
2. Đổi chỗ cột $i$ và cột $j$ của ma trận.

Ô nằm ở giao của dòng $i$ và cột $j$ được gọi là nằm dưới đường chéo chính nếu $i>j$.

Hãy đưa ma trận về dạng mà mọi số $1$ đều nằm dưới đường chéo chính, bằng cách sử dụng các thao tác trên.

Bạn không cần cực tiểu hoá số thao tác, nhưng số thao tác không được vượt quá ${10}^5$. Trong mọi thao tác, hai chỉ số $i$ và $j$ phải khác nhau. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$, kích thước của ma trận.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_k$ và $y_k$, mô tả một ô chứa số $1$ nằm ở dòng $x_k$ và cột $y_k$.

Dữ liệu đảm bảo tất cả các vị trí đã cho là đôi một khác nhau.

Dữ liệu ra

• Dòng đầu tiên in ra số nguyên không âm $m$, số thao tác cần thực hiện.
• $m$ dòng tiếp theo, mỗi dòng in ra ba số nguyên $t$, $i$, $j$: $t=1$ nếu đổi chỗ hai dòng, $t=2$ nếu đổi chỗ hai cột, còn $i$ và $j$ là chỉ số của hai dòng (hoặc hai cột) được đổi chỗ.

Ràng buộc

• $2\le n\le 1000$
• $1\le x_k,y_k\le n$
• $0\le m\le {10}^5$
• $1\le t\le 2$, $1\le i,j\le n$, $i\ne j$

Ví dụ