题目描述

在一场星际信息学奥林匹克竞赛中，参与者是大量的安卓机器人。那些设计题目、撰写题面和制作测试数据的机器人，属于科学委员会成员；负责维护电脑和软件正常运行的机器人，属于技术委员会成员。还有第三大群体——志愿者，他们参与组织和执行各种活动。

每个志愿者都有一位直接上司，分别来自科学委员会和技术委员会。科学委员会的每位成员（除了主席）也有一位直接上司，且这位上司也是科学委员会成员。技术委员会成员同理，除了主席外，每人也有一位技术委员会成员作为直接上司。

比赛开始时，会进行一系列确定所有志愿者、科学委员会成员和技术委员会成员上司的操作，过程如下：

首先，$n$ 名志愿者编号从 $1$ 到 $n$，按编号顺序排成一列。接着，$m$ 名科学委员会成员编号从 $1$ 到 $m$，依次按编号顺序挑选自己的下属。第一个科学委员会成员会选择一段连续的志愿者作为下属，这些被选中的志愿者会从队列中退出，他本人则站到他们原来的位置，替代他们的位置。第二个成员从现在的队列中选择自己的下属（可能是志愿者或已被替代的科学委员会成员），同样替代他们的位置。依此类推，直到最后一名科学委员会主席，他必须选择当前队列中所有剩余的机器人作为下属。

当科学委员会队列最终只剩下主席时，技术委员会成员重复同样的过程，起始队列是志愿者，顺序保持不变。

如果某个志愿者同时（可能不是直接）归属于一名科学委员会成员和一名技术委员会成员，则这两名成员被认为可能发生冲突。特别地，科学委员会主席和技术委员会主席总是可能冲突的。冲突的总数反映了比赛组织的质量。

请你写个程序，计算每位科学委员会成员可能与多少技术委员会成员冲突，并输出所有冲突的总数。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m, k \le 100\,000$），分别表示志愿者人数、科学委员会成员人数和技术委员会成员人数。

接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le m$，$1 \le b_i \le k$），表示第 $i$ 个志愿者在科学委员会和技术委员会中的直接上司编号。

接下来一行包含 $m-1$ 个整数 $c_i$（$i = 0 \ldots m-2$，$i < c_i \le m$），表示科学委员会第 i 个成员的直接上司编号。科学委员会主席编号为 $m$。

再接下来一行包含 $k-1$ 个整数 $d_i$（$i = 0 … k-2，i < d_i \le k$），表示技术委员会第 $i$ 个成员的直接上司编号。技术委员会主席编号为 $k$。

保证输入数据均符合题目描述的过程。

输出格式

输出一行，包含一个整数——所有可能冲突的总数。

4 3 4
1 2
1 1
2 1
2 4
3 3
3 3 4

11

提示

在示例中，只有科学委员会的第二名成员和技术委员会的第二名成员不会发生冲突。

评分

对于 $30$ 分的数据，志愿者、科学委员会成员和技术委员会成员不超过 $100$ 名。

对于 $60$ 分的数据，志愿者、科学委员会成员和技术委员会成员不超过 $5000$ 名。

翻译来源：GPT 4.1 mini。