题目思路

思路：模拟 + 排序

题目保证目标群落包含初始群落的所有菌株，且相同编号的菌株在两种群落中的父子关系完全相同。故前 $n$ 个菌株无需考虑是否相同的问题。

从目标群落的第 $n + 1$ 个菌株开始，均为新增的菌株。这些新增菌株需要满足：其父亲编号都各不相同，且父亲编号都必须小于等于 $n$，因为大于 $n$ 的编号均为新增的菌株，根据题目要求不能作为其他菌株的父亲。

为了方便判断是否有两个新增菌株的父亲相同，将所有新增菌株按其父亲编号排序，如果两个菌株的父亲编号相同，则这两个菌株在排序后必然相邻。

题目内容

科学家在实验室培养一种树状分裂的细菌群落。每一株细菌都有一个编号，初始群落形成一棵以 $1$ 号菌株为根的树，菌株之间的父子关系构成树的边。每年，每株细菌最多进行一次分裂，产生一个新的子菌株，直接连接在该菌株上。新产生的菌株不能继续分裂（即新菌株只能是叶子），也不能作为其他新菌株的父节点。换句话说，目标群落必须由初始群落经过以下操作得到：选择初始群落中的若干菌株，为每个被选中的菌株至多添加一个新的直接子菌株，且所有新菌株的父亲必须来自初始群落。

给定初始群落与一个目标群落的结构，你需要判断目标群落是否有可能恰好经过一年的分裂得到。保证目标群落包含初始群落的所有菌株，且相同编号的菌株在两种群落中的父子关系完全相同。

约束条件：

• 测试数据组数 $T$ 不超过 $10$。
• 每个群落的菌株总数 $n, m$ 满足 $1 \le n, m \le 50000$。
• 父节点编号均不大于当前节点编号。

输入描述

第一行包含一个整数 $T$，表示测试数据的组数。

对于每一组数据，包含四行： 第一行一个整数 $n$，表示初始群落的菌株数量。 第二行 $n-1$ 个整数 $f_2, f_3, \dots, f_n$，其中 $f_i$ 表示初始群落中编号为 $i$ 的菌株的父节点编号（若 $n=1$ 则该行为空）。 第三行一个整数 $m$，表示目标群落的菌株数量。 第四行 $m-1$ 个整数 $g_2, g_3, \dots, g_m$，其中 $g_i$ 表示目标群落中编号为 $i$ 的菌株的父节点编号（若 $m=1$ 则该行为空）。

数据保证对于所有 $2 \le i \le n$，有 $f_i = g_i$，即初始群落是目标群落的子结构。

输出描述

对于每组数据，输出一行，如果目标群落可以通过一年的分裂得到，输出 "yes"，否则输出 "no"。

样例1

输入

1
2
1
3
1 2

输出

yes

说明

初始群落有 $2$ 个菌株，编号 1 和 2，其中 1 为根，2 的父亲是 1。目标群落有 $3$ 个菌株，原有的 1、2 关系不变，新增菌株 3 的父亲为 2。检查新增节点：新增节点仅有一个，其父亲 2 属于初始群落（编号 $\le n$），且 2 没有其他新增子节点。这满足一年内 2 号菌株进行一次分裂的条件，因此输出 yes。

样例2

输入

1
2
1
4
1 2 2

输出

no

说明

初始群落有 1 和 2。目标群落新增了 3 和 4 两个菌株，它们的父亲都是 2。由于每株细菌每年最多分裂一次，初始菌株 2 试图产生两个新子节点，违反了限制，因此输出 no。

样例3

输入

1
2
1
4
1 1 3

输出

no

说明

初始群落有 1、2。目标群落新增 3（父亲 1）和 4（父亲 3）。新菌株 4 的父亲 3 是本次分裂新增的菌株，并非初始群落成员。题目要求新菌株的父亲必须来自初始群落，且新菌株不能作为其他新菌株的父亲，所以不合法，输出 no。

样例4

输入

1
1

1

输出

yes

说明

初始群落与目标群落均只包含菌株 1，没有任何新增节点。一年内可以不发生任何分裂，这符合每株细菌“最多进行一次分裂”（即可以不分裂）的条件，因此输出 yes。