Problem Description

In an Interstellar Informatics Olympiad, the participants are a large number of android robots. The robots that design the problems, write the statements, and produce the testdata are members of the Scientific Committee. The robots responsible for keeping the computers and software running properly are members of the Technical Committee. There is also a third large group—volunteers, who help organize and carry out various activities.

Each volunteer has two direct supervisors, one from the Scientific Committee and one from the Technical Committee. Each member of the Scientific Committee (except the chairman) also has a direct supervisor, and that supervisor is also a member of the Scientific Committee. The same holds for the Technical Committee: except for the chairman, everyone has a direct supervisor who is also a Technical Committee member.

Before the contest starts, a series of operations is performed to determine the supervisors of all volunteers and committee members, as follows:

First, $n$ volunteers numbered from $1$ to $n$ stand in a line in increasing order. Then, $m$ members of the Scientific Committee numbered from $1$ to $m$ choose their subordinates in order of their numbers. The first Scientific Committee member chooses a contiguous segment of volunteers as subordinates; these chosen volunteers leave the line, and the member stands in their original position, replacing them. The second member chooses their subordinates from the current line (which may contain volunteers or already placed Scientific Committee members) and likewise replaces them. This continues until the last Scientific Committee member, the chairman, who must choose all remaining robots in the current line as subordinates.

When the Scientific Committee line ends up containing only the chairman, the Technical Committee members repeat the same process, starting from the volunteers in the same order.

If a volunteer belongs (not necessarily directly) to both a Scientific Committee member and a Technical Committee member, then these two members are considered to be potentially in conflict. In particular, the Scientific Committee chairman and the Technical Committee chairman are always potentially in conflict. The total number of conflicts reflects the quality of the contest organization.

Write a program to compute, for each Scientific Committee member, how many Technical Committee members they may be in conflict with, and output the total number of conflicts.

Input Format

The first line contains three integers $n$, $m$, and $k$ ($1 \le n, m, k \le 100\,000$), representing the number of volunteers, the number of Scientific Committee members, and the number of Technical Committee members.

The next $n$ lines each contain two integers $a_i$ and $b_i$ ($1 \le a_i \le m$, $1 \le b_i \le k$), meaning that the $i$-th volunteer’s direct supervisors are member $a_i$ in the Scientific Committee and member $b_i$ in the Technical Committee.

The next line contains $m-1$ integers $c_i$ ($i = 0 \ldots m-2$, $i < c_i \le m$), meaning that member $i$ of the Scientific Committee has direct supervisor $c_i$. The Scientific Committee chairman is numbered $m$.

The next line contains $k-1$ integers $d_i$ ($i = 0 \ldots k-2$, $i < d_i \le k$), meaning that member $i$ of the Technical Committee has direct supervisor $d_i$. The Technical Committee chairman is numbered $k$.

It is guaranteed that the input data satisfies the process described in the statement.

Output Format

Output one line containing one integer: the total number of potential conflicts.

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

11

Hint

In the sample, only the second member of the Scientific Committee and the second member of the Technical Committee do not have a conflict.

Scoring

For $30$ points, the numbers of volunteers, Scientific Committee members, and Technical Committee members do not exceed $100$.

For $60$ points, the numbers of volunteers, Scientific Committee members, and Technical Committee members do not exceed $5000$.

Translation source: GPT 4.1 mini.

Translated by ChatGPT 5