题目描述

Miyuki 有一棵由 $N$ 个节点组成的树，节点编号为 $1$ 到 $N$。他希望通过若干次“折叠”操作，把这棵树变成一个星形树。

这里，经过 $K$ 次操作后，树的大小会变成 $N-K$。一个大小为 $N-K$ 的树若至少有 $N-K-1$ 个叶子节点，就称为星形树。叶子节点指恰好有一个邻居的节点。

第 $i$ 次折叠操作如下：

1. 在当前树中选择两个不同节点 $a_i,b_i$；
2. 令 $V$ 为 $a_i$ 或 $b_i$ 的所有邻居组成的集合；
3. 若 $a_i,b_i$ 本身出现在 $V$ 中，则从 $V$ 中删除它们；
4. 从树中删除节点 $a_i,b_i$ 以及所有与它们相连的边；
5. 加入一个新节点，编号为 $N+i$；
6. 将新节点 $N+i$ 与 $V$ 中的每个节点连边。

每次操作后，得到的图必须仍然是一棵树；也就是说，操作不能产生环。若会产生环，则该操作非法，不能执行。

Miyuki 希望使用最少次数的折叠操作，将原树变成星形树。请你输出：

1. 最小操作次数 $K$；
2. 一组可以达到该最小次数的 $K$ 次操作。

输入格式

第一行输入一个整数 $N$，表示初始树的节点数。

接下来 $N-1$ 行，每行输入两个整数 $u_i,v_i$，表示树上的一条边。

输出格式

第一行输出一个整数 $K$，表示最少需要执行的折叠操作次数。

接下来 $K$ 行，每行输出两个整数 $a_i,b_i$，表示第 $i$ 次折叠操作选择的两个节点。

若有多种合法答案，输出任意一种即可。

数据范围与约束

• $1\le N\le 500000$；

子任务

样例 1

输入

5
1 2
2 3
3 4
4 5

输出

1
2 4

解释

执行一次折叠，选择节点 $2$ 和 $4$。

它们的邻居集合为 $V=\{1,3,5\}$。删除节点 $2,4$ 后，加入新节点 $N+1=6$，并加入边 $(1,6),(3,6),(5,6)$。

最终树由节点 $1,3,5,6$ 和上述三条边组成，是一棵星形树。

样例 2

输入

6
1 2
2 3
3 4
4 5
5 6

输出

2
2 4
5 7

解释

先折叠 $(2,4)$，加入节点 $7$；再折叠 $(5,7)$，加入节点 $8$。

最终树由节点 $1,3,6,8$ 组成，边为 $(1,8),(3,8),(6,8)$，是一棵星形树。