树形 DNA

现在是 4202 年，人类成功在距离地球 9180 光年外的区域找到了地外生物，并且通过 Lutece 号飞船将这些宝贵的生物样本带回了地球。

在经过一段研究后，研究人员发现这些生物也使用脱氧核苷酸作为遗传物质的组成单元。但是它们的脱氧核苷酸分子和地球生物的并不完全相同：地球生物的遗传物质 DNA 是呈双螺旋链型存在的，而它们的则是呈类似二叉树的结构存在的。

一种地外生物的核苷酸分子如下图所示：



现在研究人员想要进一步研究这些地外生物的遗传因子。他们发现这种树形遗传物质的某些连通的区域是值得研究的，比方说这一区域用于指导某种蛋白质的合成。于是他们想获得这样的区域在整个遗传物质树中出现的具体位置。不过很可惜，这些生物学者并不太擅长编程。他们于是向你求助，并且给了你如下简化后的问题。

给定一棵二叉树 $S$ 和 $T$。若对于 $S$ 的一棵子树 $S'$，删除若干个（可以不删）$S'$ 的子树后和 $T$ 相同，则称 $T$ 与 $S'$ 匹配。求 $S$ 所有和 $T$ 匹配的子树。此外，由于游离的磷酸基团会影响分子结构的稳定性，所以 $T$ 中叶子节点的数量不会大于 $20$。

在这里，两棵树相同定义为两棵树均非空，且如果两棵树左和右儿子都分别相同。若其中一棵树没有左或右儿子，则另一棵树也必须没有。请注意，这里的两棵子树并不等价。即若对于 $S$ 和 $T$，$S$ 只有左子树 $S'$，$T$ 只有右子树 $T'$，即使 $S'$ 和 $T'$ 相同，$S$ 和 $T$ 也不相同。

第一行一个整数 $T$（$1\le T\le 10^3$），表示数据组数。

对于每组数据，第一行一个整数 $n$（$1\le n\le 3\times 10^5$），表示 $S$ 中的节点数量。节点编号为 $0,1,2,\ldots,n-1$，其中 $0$ 为根节点。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_{i-1}$ 和 $r_{i-1}$（$0\le l_{i-1},r_{i-1} < n$），表示编号为 $i-1$ 的节点的左右儿子节点的编号。特别的，如果 $l_{i-1}=0$ 或 $r_{i-1}=0$，由于 $0$ 号节点一定是根节点，故此时表示的是第 $i-1$ 号节点没有左子树或右子树。

接下来一行包含一个整数 $m$（$1\le m\le 3\times 10^5$），表示 $T$ 中的节点数量。节点编号为 $0,1,2,\ldots,m-1$，其中 $0$ 为根节点。

接下来 $m$ 行输入 $T$ 中每个节点的左右儿子编号，格式与 $S$ 的相同。

保证对于所有数据点，$n$ 之和与 $m$ 之和都不会大于 $2\times 10^6$。并且保证每组数据中 $T$ 的叶子节点数量不会大于 $20$。

对于每组数据，首先输出一个数字 $k$，表示 $T$ 在 $S$ 中的匹配次数。接下来的一行包含 $k$ 个整数，表示与 $T$ 相匹配的 $S$ 子树的根节点编号，按照节点编号升序排序。

特别地，$k=0$ 时也要输出一个空行。

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

3
0 1 2
1
0

2024“钉耙编程”中国大学生算法设计超级联赛（6）