← 返回题目列表

Codeforces · 266/C

C. 对角线下方

中文机器翻译题面 查看原题

给定一个由 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