CF2257C.Spying on the Beaver

You are given a rooted tree$^{\text{∗}}$ with $n$ vertices, numbered from $1$ to $n$. The vertex numbered $1$ is the root of the tree. The Beaver, initially located at the root, travels through the tree to one of the beaver dams located at the vertices numbered $a_1, \ldots, a_m$.

You need to determine which of these $m$ vertices the Beaver went to. To do this, you can place cameras on any edges of the tree. If the Beaver traverses an edge with a camera on it, you will see this. For clarity, we assume that after all the Beaver's movements, you will receive a sequence of edges with cameras in which the Beaver was observed passing through the corresponding edge.

Since cameras are expensive, it is necessary to use the minimum number of them sufficient to uniquely determine the Beaver's destination. You are required to state the minimum necessary number of cameras $k$ and the edges on which they should be placed.

$^{\text{∗}}$A rooted tree is a tree where one vertex is special and called the root.

你被给定一棵有 $n$ 个顶点的有根树$^{\text{∗}}$，顶点编号为 $1$ 到 $n$。编号为 $1$ 的顶点是该树的根。河狸最初位于根节点，并沿树中路径前往位于顶点 $a_1, \ldots, a_m$ 处的某一座河狸水坝。

你需要确定河狸最终到达了这 $m$ 个顶点中的哪一个。为此，你可以在树的任意边上安装摄像头。若河狸经过一条装有摄像头的边，则你会观测到这一事件。为明确起见，我们假设：在河狸完成全部移动后，你将收到一个边序列（即所有装有摄像头且被河狸经过的边），按河狸经过它们的顺序排列。

由于摄像头价格昂贵，必须使用尽可能少的摄像头，且其数量须足以唯一确定河狸的目的地。你需要给出所需的最少摄像头数量 $k$，以及应安装摄像头的具体边。

$^{\text{∗}}$有根树是指树中指定一个特殊顶点作为根的树。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.

In the first line of each test case, there is a single integer $n$ ($2 \le n \le 10^5$).

The second line contains $n-1$ integers $p_2, \ldots, p_n$ — the parents of the vertices from the $2$nd to the $n$th ($1 \le p_i \lt i$; $2 \le i \le n$).

The third line contains a single integer $m$ — the number of vertices containing beaver dams ($1 \le m \le n$).

In the fourth line, there are $m$ integers $a_1, \ldots, a_m$ — the numbers of these vertices ($1 \le a_i \le n$; $1 \le i \le m$). All $a_i$ are distinct.

It is guaranteed that the sum of $n$ across all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2 \cdot 10^4$）。随后是各测试用例的描述。

在每个测试用例的第一行中，有一个整数 $n$（$2 \le n \le 10^5$）。

第二行包含 $n-1$ 个整数 $p_2, \ldots, p_n$ —— 分别为第 $2$ 个到第 $n$ 个顶点的父节点（$1 \le p_i \lt i$；$2 \le i \le n$）。

第三行包含一个整数 $m$ —— 含有海狸水坝的顶点数量（$1 \le m \le n$）。

第四行包含 $m$ 个整数 $a_1, \ldots, a_m$ —— 这些顶点的编号（$1 \le a_i \le n$；$1 \le i \le m$）。所有 $a_i$ 互不相同。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, output exactly one line. First, output the number $k$ — the minimum required number of cameras, and then, in the same line, for each of the $k$ edges connecting the vertices $u$ and $p_u$, where cameras need to be installed, output the vertex number $u$.

If there are multiple answers, you can output any one of them.

对于每个测试用例，输出恰好一行。首先输出数字 $k$ —— 所需摄像头的最少数量；然后在同一行中，对需要安装摄像头的 $k$ 条边（每条边连接顶点 $u$ 与 $p_u$），依次输出顶点编号 $u$。

若存在多个合法答案，输出其中任意一个即可。

In the first test case, we do not need to install any cameras because there is only one dam in the tree, and the Beaver will definitely go there.

In the second test case, it is necessary to place a camera on each edge because there is a dam located at each vertex.

In the third test case, the dams are located in two adjacent vertices, so by placing a camera on the edge between these vertices, we can uniquely determine which one the Beaver went to.

在第一个测试用例中，我们无需安装任何摄像头，因为树中仅有一个水坝，海狸必定会前往该处。

在第二个测试用例中，必须在每条边上都安装一个摄像头，因为每个顶点上均设有一个水坝。

在第三个测试用例中，水坝位于两个相邻的顶点上，因此只需在连接这两个顶点的边上安装一个摄像头，即可唯一确定海狸前往的是哪一个顶点。