P12803 [AMPPZ 2019] Little Worm

Source: [AMPPZ 2019](https://amppz.tcs.uj.edu.pl/2019/data.html).

小虫住在一棵树上。 这棵树有 $ 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 $ 的正确序列（特别地，你不需要最小化移动次数）。 假设小虫是对称的——它可以向两个方向移动，并且可以以任意一端朝向进入目标路径。