给定一棵包含 $n$ 个顶点的树。你可以重复执行以下操作至多 $10^5$ 次：

• 选择四个不同的顶点 $1 \le v_1, v_2, v_3, v_4 \le n$，使得存在连接 $v_1$ 与 $v_2$、 $v_2$ 与 $v_3$、以及 $v_3$ 与 $v_4$ 的边。移除这些边，并添加连接 $v_1$ 与 $v_3$、 $v_1$ 与 $v_4$ 以及 $v_2$ 与 $v_4$ 的边。

你的任务是变换给定的树，使其直径至多为 $3$。请找到一个满足条件的变换操作序列。

输入格式

第一行包含一个整数 $n$ ($4 \le n \le 100$)。

接下来的 $n-1$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n; x_i \neq y_i$ 对于 $1 \le i \le n-1$)，表示第 $i$ 条边连接树中的顶点 $x_i$ 和 $y_i$。

你可以假设给定的边构成一棵树。

输出格式

第一行输出 $k$，表示操作次数 ($0 \le k \le 10^5$)。

在接下来的 $k$ 行中，每行输出四个由空格分隔的整数 $v_1, v_2, v_3, v_4$。这些值 $v_1, v_2, v_3, v_4$ 必须满足上述条件。

如果存在多种解，输出其中任意一种即可。可以证明至少存在一种方法可以达到目标。

注意，你不需要最小化 $k$。

样例

样例输入 1

6
1 2
2 3
3 4
4 5
5 6

样例输出 1

3
4 3 2 1
6 5 4 1
2 4 6 1

说明

两个顶点 $u$ 和 $v$ 之间的距离定义为从 $u$ 到 $v$ 的唯一简单路径上的边数。

树的直径是任意两个顶点之间的最大距离。