International Chemical Producing Company (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