Background

我是小 j，我有一道组合题，和一棵树 $G(V, E)$。

Description

你要在图 $G$ 上玩一个操作游戏，每次操作你先置 $G' = G$，然后选择一个顶点 $v \in V$，给 $G'$ 加入一个顶点 $v'$；之后你要对于 $\forall u \in V, (u, v) \in E$，给 $G'$ 加入一条边 $(u, v')$；最后把 $G$ 替换为 $G'$，开始下一轮操作。

当然你一直这样操作下去也没有意思。所以某次操作开始前，若 $G$ 存在一条哈密顿路，我就会把游戏终止。哈密顿路呢就是说从任意点出发、不重复地经过所有点、以任意点结束的一条简单路径。

现在我要你求出最少的操作次数及对应的步骤，使得游戏终止。众所周知判断图是否存在哈密顿路是 NPC 问题，所以你得报告一条哈密顿路。

Format

Input

第一行一个整数 $n$，那么 $G$ 的顶点集初始为 $\{V_1, V_2, \ldots, V_n\}$。下面 $n - 1$ 行，每行两个整数 $(a, b)$，表示 $(V_a, V_b) \in E$。

Output

第一行一个整数，表示所求的最少操作次数 $g$。$g$ 是一个有限的数，我可以明确地告诉你这一点。

第二行 $g$ 个整数 $u_1, u_2, \ldots, u_g$，那么第 $i$ 次操作是选择 $v = V_{u_i}$，$v' = V_{n+i}$，容易看出 $1 \leq u_i \leq n+i-1$。

最后一行 $n + g$ 个整数 $p_1, p_2, \ldots, p_{n+g}$，表示终止时发现了一条哈密顿路 $V_{p_1} \to V_{p_2} \to \ldots \to V_{p_{n+g}}$。

Samples

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

2  
5  5  
4  2  9  3  8  7  5  1  6

Limitation

对所有数据，保证 $3 \leq n \leq 100$。 对于每个数据点，如果你的答案只有 $g$ 正确，那么你可以获得 $60\%$ 的分数，但注意这种情况下你需要输出一个格式正确的答案，即输出了数量正确的数且满足 $1 \leq u_i \leq n + i - 1, 1 \leq p_i \leq n + g$，否则会被判为 $0$ 分；如果你的答案 $g$ 不正确，但你的操作方案合法且 $g \leq 10^4$，你同样可以获得 $60\%$ 的分数；你在每个子任务的得分是每个数据点得分的最小值。

$n \leq 5$（15 分）； $n \leq 10$（15 分）； 第 $i(1 \leq i < n)$ 条边连接 $V_i$ 和 $V_{i+1}$（15 分）； 第 $i(1 \leq i < n)$ 条边连接 $V_1$ 和 $V_{i+1}$（15 分）； 第 $i(1 \leq i < n)$ 条边连接 $V$ 和 $V_{i+1}$（10 分）； 每个点最多和 $3$ 个其他顶点相连（10 分）； $n \leq 20$（10 分）； 没有特殊性质（10 分）。