P14023 [ICPC 2024 Nanjing R] Social Media

On a social media platform, users can leave comments under others' posts to express their thoughts. However, these comments are not visible to everyone. Specifically, for user $C$ to see user $A$'s comments under user $B$'s post, he/she has to be friends with both $A$ and $B$ at the same time. If a user leaves a comment under his/her own post, all his/her friends can see this comment. As an active user on this platform, you would like to see as many comments as possible. There are $k$ users (not counting you) on the platform, numbered from $1$ to $k$. There are also $m$ comments on the platform, but you might not be able to see them all because you only have $n$ friends. As you need to participate in the 2024 ICPC Asia Nanjing Regional Contest, you don't have time to make too many new friends. What's the maximum number of comments you can see if you make at most two new friends on the platform?

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le k \le 2 \times 10^5$, $1 \le m \le 2 \times 10^5$) indicating the number of your friends, the number of comments, and the number of users (not counting you) on the platform. The second line contains $n$ distinct integers $f_1, f_2, \cdots, f_n$ ($1 \le f_i \le k$) indicating your friends on the platform. For the following $m$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le k$) indicating a comment written by user $a_i$ under user $b_i$'s post. It's guaranteed that neither the sum of $k$ nor the sum of $m$ of all test cases will exceed $2 \times 10^5$.

For each test case, output one line containing one integer, indicating the maximum number of comments you can see if you make at most two new friends on the platform.

For the first sample test case, you can make friends with user $1$ and $4$. For the second sample test case, you can make friends with user $5$ and $6$. For the third sample test case, you can make friends with user $2$. For the fourth and fifth sample test cases, you don't need to make new friends because you can already see all comments.