C. Ниже диагонали
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана квадратная матрица, состоящая из n строк и n столбцов. Будем считать, что строки пронумерованы целыми числами от 1 до n сверху вниз, а столбцы пронумерованы целыми числами от 1 до n слева направо. Некоторые клетки матрицы (всего n - 1 клеток) содержат единицы, остальные клетки — нули. Разрешается производить над матрицей следующие операции:

  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. Если существует несколько решений, выведите любое.

Примеры
Входные данные
2
1 2
Выходные данные
2
2 1 2
1 1 2
Входные данные
3
3 1
1 3
Выходные данные
3
2 2 3
1 1 3
1 1 2
Входные данные
3
2 1
3 2
Выходные данные
0