题目背景

Source: AMPPZ 2019.

题目描述

小虫住在一棵树上。 这棵树有 $n$ 个顶点（并且是一个连通的、无向的无环图），小虫占据了顶点 $a$ 和 $b$ 之间的整条路径。

小虫想移动到另一条路径——顶点 $c$ 和 $d$ 之间的那条路径——因为那里阳光更充足。 已知路径 $a \leftrightarrow b$ 和 $c \leftrightarrow d$ 没有公共顶点。

为了改变它在树上的位置，小虫可以进行一些移动，这些移动包括让小虫的任意一端进入一个空闲顶点。 形式化地说，如果小虫当前占据 $x$ 和 $y$ 之间的路径，它可以选择一个与 $x$ 相邻的新顶点 $z$，该顶点不在路径 $x \leftrightarrow y$ 上。 然后小虫释放（停止占据） $y$ ，改为占据 $z$ 。 类似地，小虫可以选择一个与 $y$ 相邻的顶点 $z'$ ，释放 $x$ 并占据 $z'$ 。 在一次移动后，小虫仍然占据着某条路径，并且其长度不变。

小虫的目标是到达 $c$ 和 $d$ 之间的路径，但由于相当懒惰，它计划移动不超过 $10 \cdot n$ 次。 你能帮助它在不超过该限制的情况下达到目标吗？

输入格式

本题单个测试点内有多组测试数据。

输入的第一行包含测试数据的组数 $z$ ($1 \leq z \leq 7000$)。测试数据组随后给出，每组格式如下：

• 测试数据的第一行包含一个整数 $n$ ($4 \leq n \leq 100\,000$) —— 树的顶点数。 接下来的 $n - 1$ 行每行包含两个整数 $u, v$ ($1 \leq u \ne v \leq n$)，描述一条边的两个端点。
• 下一行给出两个整数 $a$ 和 $b$ ($1 \leq a \ne b \leq n$)。 这些是小虫起始位置路径的端点。
• 下一行包含小虫目标路径的端点，以两个整数 $c$ 和 $d$ ($1 \leq c \ne d \leq n$) 给出。

$a$ 和 $b$ 之间路径上的顶点数与 $c$ 和 $d$ 之间路径上的顶点数相同。 你也可以假设这两条路径没有公共顶点。

所有测试数据的 $n$ 值之和不超过 $1\,000\,000$。

输出格式

对于每组测试数据，如果小虫不能在 $10 \cdot n$ 次移动内达到目标，则输出 $-1$。 否则，在两行中输出小虫移动的一种可能序列：

• 第一行：移动次数 $q$ ($1 \leq q \leq 10 \cdot n$)，
• 第二行： $q$ 个整数 $v_1, v_2, \ldots, v_q$ —— 所需的移动序列。

对于 $i = 1, 2, \ldots, q$，值 $v_i$ 应表示第 $i$ 次移动中小虫进入的顶点。

你可以输出任何将小虫移动到目标路径且移动次数不超过 $10 \cdot n$ 的正确序列（特别地，你不需要最小化移动次数）。 假设小虫是对称的——它可以向两个方向移动，并且可以以任意一端朝向进入目标路径。

3
6
1 2
1 3
1 4
4 5
4 6
2 3
5 6
15
1 2
1 6
2 3
2 4
2 5
6 7
6 8
5 9
6 10
9 11
9 12
9 13
12 14
14 15
14 13
3 6
6
1 2
1 3
2 4
4 5
5 6
4 6
3 2

-1
7
15 5 2 1 6 7 3
3
2 1 3