CF266C.Below the Diagonal

You are given a square matrix consisting of n rows and n columns. We assume that the rows are numbered from 1 to n from top to bottom and the columns are numbered from 1 to n from left to right. Some cells (n - 1 cells in total) of the the matrix are filled with ones, the remaining cells are filled with zeros. We can apply the following operations to the matrix:

1. Swap i-th and j-th rows of the matrix;
2. Swap i-th and j-th columns of the matrix.

You are asked to transform the matrix into a special form using these operations. In that special form all the ones must be in the cells that lie below the main diagonal. Cell of the matrix, which is located on the intersection of the i-th row and of the j-th column, lies below the main diagonal if i > j.

给你一个由 $n$ 行和 $n$ 列组成的方阵。我们假设行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。该矩阵中恰好有 $n-1$ 个单元格填入了数字 $1$，其余单元格均填入数字 $0$。你可以对矩阵执行以下两种操作：

1. 交换矩阵的第 $i$ 行与第 $j$ 行；
2. 交换矩阵的第 $i$ 列与第 $j$ 列。

要求你通过上述操作将矩阵变换为一种特殊形式：在该特殊形式中，所有数字 $1$ 必须位于主对角线下方的单元格中。矩阵中位于第 $i$ 行与第 $j$ 列交叉处的单元格位于主对角线下方，当且仅当 $i > j$。

The first line contains an integer n (2 ≤ n ≤ 1000) — the number of rows and columns. Then follow n - 1 lines that contain one's positions, one per line. Each position is described by two integers x__k, y__k (1 ≤ x__k, y__k ≤ n), separated by a space. A pair (x__k, y__k) means that the cell, which is located on the intersection of the x__k-th row and of the y__k-th column, contains one.

It is guaranteed that all positions are distinct.

第一行包含一个整数 $n$（$2 \leq n \leq 1000$）—— 表示行数与列数。随后是 $n-1$ 行，每行描述一个数字 1 的位置。每个位置由两个整数 $x_k$、$y_k$（$1 \leq x_k, y_k \leq n$）表示，二者以空格分隔。一对 $(x_k, y_k)$ 表示位于第 $x_k$ 行与第 $y_k$ 列交点处的单元格中包含数字 1。

保证所有位置互不相同。

Print the description of your actions. These actions should transform the matrix to the described special form.

In the first line you should print a non-negative integer m (m ≤ 105) — the number of actions. In each of the next m lines print three space-separated integers t, i, j (1 ≤ t ≤ 2, 1 ≤ i, j ≤ n, i ≠ j), where t = 1 if you want to swap rows, t = 2 if you want to swap columns, and i and j denote the numbers of rows or columns respectively.

Please note, that you do not need to minimize the number of operations, but their number should not exceed 105. If there are several solutions, you may print any of them.

输出你所执行操作的描述。这些操作应将矩阵变换为题目所描述的特殊形式。

第一行输出一个非负整数 $m$（$m \leq 10^5$），表示操作的数目。接下来的 $m$ 行中，每行输出三个用空格分隔的整数 $t,\ i,\ j$（其中 $1 \leq t \leq 2$，$1 \leq i,\ j \leq n$，且 $i \neq j$）：若 $t = 1$，表示交换第 $i$ 行与第 $j$ 行；若 $t = 2$，表示交换第 $i$ 列与第 $j$ 列。

请注意，你无需最小化操作次数，但操作总数不得超过 $10^5$。若存在多种可行解，输出任意一种即可。