Construct the Tree Using Operations

Given an integer (n) and a tree with (n) nodes numbered from (1) to (n), as well as an initially empty graph with (n) vertices and an integer sequence (a_1, a_2, \dots, a_n) (all initially zero), you are allowed to perform the following two types of operations any number of times:

1. Operation 1 x y: Set (a_x = y). It is guaranteed that for all type-1 operations, the values of (y) are distinct.
   
2. Operation 2 x y: Add an edge connecting the vertices numbered (a_x) and (a_y). It is guaranteed that both (a_x) and (a_y) are nonzero when this operation is performed.
   
   Your task is to output a sequence of operations that, when executed in order, constructs the given tree. The constructed graph must be a tree, i.e. it should have exactly (n-1) edges, be connected, and contain no duplicate edges or self-loops.
   
   Note: You may output any valid sequence of operations that builds the tree.

inputFormat

The first line contains an integer (n) ((2 \le n \le 10^5)), the number of nodes in the tree. Each of the following (n-1) lines contains two integers (u) and (v), representing an edge of the tree.

outputFormat

First, output a single integer (m) — the total number of operations. Then output (m) lines, each representing an operation in the order they should be performed. Each operation must be in one of the following formats:

• For type-1 operations: 1 x y (here, (x) is the index in the array and (y) is the unique value assigned to (a_x)).
• For type-2 operations: 2 x y (here, (x) and (y) are indices such that (a_x) and (a_y) have been set to nonzero values).

A simple valid strategy is to first assign (a_i = i) for (i = 1, 2, \dots, n) using type-1 operations, and then for each tree edge ((u, v)), perform a type-2 operation using indices (u) and (v).

sample

3
1 2
2 3

5
1 1 1
1 2 2
1 3 3
2 1 2
2 2 3