给定一个由 n 行和 n 列组成的方阵。我们假设行从上到下编号为 1 到 n,列从左到右编号为 1 到 n。矩阵的一些单元格(总共 n - 1 个单元格)用 1 填充,其余单元格用 0 填充。我们可以对矩阵进行以下运算:
1.交换矩阵的第i行和第j行;
2. 交换矩阵的第 i 列和第 j 列。
要求您使用这些运算将矩阵转换为特殊形式。在这种特殊形式中,所有的单元格都必须位于主对角线下方的单元格中。如果 i > j,则位于第 i 行和第 j 列交叉点的矩阵单元位于主对角线下方。
输入
第一行包含一个整数 n (2 ≤ n ≤ 1000) — 行数和列数。然后跟随 n - 1 行包含一个人的位置,每行一个。每个位置由两个整数 xk, yk (1 ≤ xk, yk ≤ n) 描述,并用空格分隔。一对 (xk, yk) 表示位于第 xk 行和第 yk 列交叉处的单元格包含一个。
保证所有位置都是不同的。
输出
打印您的操作说明。这些动作应该将矩阵转换为所描述的特殊形式。
在第一行中,您应该打印一个非负整数 m (m ≤ 105) — 操作数。在接下来的 m 行中,每行打印三个空格分隔的整数 t, i, j (1 ≤ t ≤ 2, 1 ≤ i, j ≤ n, i ≠ j),其中如果要交换行,则 t = 1;如果要交换列,则 t = 2;i 和 j 分别表示行数或列数。
请注意,您不需要最小化操作次数,但操作次数不应超过 105。如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
2 1 2
输出 #1
2 2 1 2 1 1 2
输入 #2
3 3 1 1 3
输出 #2
3 2 2 3 1 1 3 1 1 2
输入 #3
3 2 1 3 2
输出 #3
0