题目背景

题目描述

给定一个 $n$ 个节点的树，点编号从 $1$ 到 $n$。

你有一个 $n$ 个点初始无边的图，点编号从 $1$ 到 $n$，以及一个初始均为 $0$ 的整数序列 $a_1,a_2,\cdots,a_{12}$。

你可以进行任意次操作，操作有如下两种类型：

• 1 x y：把 $a_x$ 赋值为 $y$。需要保证在所有 1 操作中，$y$ 互不相同。
• 2 x y：连接编号为 $a_x$ 与 $a_y$ 的点。需要保证两者均不为 $0$。

请你构造这棵树，不能有重边、自环。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行每行两个正整数 $u,v$，表示在给定的树中节点 $u$ 与 $v$ 间有连边。

输出格式

第一行输出操作次数 $m$。

接下来 $m$ 行，每行输出操作 1 x y 或操作 2 x y。

3
1 2
1 3

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

提示

「数据范围」

本题采用捆绑测试与 Special Judge。

对于所有测试数据，保证：

• $1 \leq n \leq 4 \times 10^5$。
• $1 \leq u,v \leq n$。