国际化学品生产公司（ICPC）是一家制造各种化学品的跨国公司。公司建造了若干化学品储藏室，并修建了短铁路连接两个储藏室，以便搬运化学品。这些化学品储藏室和铁路构成的网络是一个特殊的树状图，其中所有节点到中心路径的距离均不超过 2。我们将每个节点从 1 开始依次编号。图 1 展示了一个网络示例。

图 1：化学品储藏室和铁路构成的网络示例。

每种化学产品都存放在储藏室的罐子里。由于化学品可能会泄漏到空气中，安全规则规定，化学品不能放置在两个相邻的储藏室中，以避免化学品之间发生不良反应。图 2 给出了两个化学品放置网络的示例：（a）是安全的，（b）是不安全的。

图 2：两个化学品放置网络示例：（a）安全，（b）不安全。

有时，工人必须清理储藏罐并将一些化学品移动到其他储藏室。Peter 是一名工人，他的经理会分配给他一项任务，包含两个安全放置网络：源网络 $T_s$ 和目标网络 $T_d$。如果存在一种可能的策略，能够遵循安全规则将化学品从 $T_s$ 移动到 $T_d$，则称该任务是“可行”的；否则，称其为“不可行”。注意，我们并不限制化学品必须放置在特定的储藏室中。如果 $T_s$ 和 $T_d$ 相同，该任务也被视为可行。图 3 和图 4 分别展示了可行任务和不可行任务的示例。

图 3：一个可行任务：（a）源网络，（b）将化学品从 4 移动到 5，（c）将化学品从 1 移动到 2，（d）将化学品从 2 移动到 3，（e）将化学品从 5 移动到 4，到达目标网络。

图 4：一个不可行任务：（a）源网络，（b）目标网络。

请编写一个程序来帮助 Peter 判断任务是否可行。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。每个测试用例包含四行。对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，其中 $n$ 表示化学品储藏室的数量，$m$ 表示化学品的数量；第二行包含 $n-1$ 个整数 $r_1, r_2, \dots, r_{n-1}$，表示对于 $1 \le i \le n-1$，储藏室 $i+1$ 与储藏室 $r_i$ 之间有一条铁路；第三行包含 $m$ 个整数 $s_j$（$1 \le j \le m$），表示源网络中化学品放置的储藏室编号；第四行包含 $m$ 个整数 $d_k$（$1 \le k \le m$），表示目标网络中化学品放置的储藏室编号。

输出格式

对于每个测试用例，如果任务可行，输出 1，否则输出 0，每个结果占一行。

技术规格

• $5 \le t \le 10$
• $1 \le m \le n \le 10,000$
• $1 \le r_i < i + 1$，$1 \le i \le n - 1$
• $1 \le s_j \le n$ 且当 $p \neq q$ 时 $s_p \neq s_q$
• $1 \le d_k \le n$ 且当 $p \neq q$ 时 $d_p \neq d_q$

样例

输入格式 1

6
4 2
1 2 2
1 4
3 4
4 2
1 2 2
1 4
1 4
5 2
1 2 2 4
1 4
3 4
11 4
1 2 3 4 5 2 4 3 5 8
1 6 7 8
1 3 5 8
11 4
1 2 3 4 5 2 4 3 5 8
1 3 5 8
7 8 9 10
10 5
1 2 3 4 2 3 3 6 4
2 4 7 8 9
1 5 6 7 8

输出格式 1

0
1
1
0
1
1