B3712.md

[语言月赛202302] 大碗宽面

题目描述

算上扶苏，本次派对共有 $n$ 个人。但是，并不是任何两个人都互相认识，并且互相认识的人关系也未必好。

具体而言，任意两个人可能是如下三种关系之一：

1. 敌人
2. 朋友
3. 陌生人

派对的一大重要活动是相互握手。对任意两个人 $u,v$，他们之间的握手情况遵循下面的规则：

1. 如果 $u$ 和 $v$ 是朋友关系，那么他们一定握手一次。
2. 如果 $u$ 和 $v$ 是敌人关系，那么他们一定不握手。
3. 如果 $u$ 和 $v$ 是陌生人关系，且存在一个人 $w$，使得 $w$ 是 $u$ 和 $v$ 之一的朋友，同时是 $u,v$ 中另一人的敌人，则 $u$ 和 $v$ 不会握手，否则 $u$ 和 $v$ 一定握手一次。

对第三条规则，简单的说法是：一对陌生人之间，如果某一方的朋友是另一方的敌人，则不握手，否则握手。

已知共有 $p$ 对人是朋友关系，$q$ 对人是敌人关系。除了这 $p + q$ 对人，其他每对人均为陌生人关系。

请你求出本次派对一共握手了多少次。

输入格式

第一行是三个整数，依次表示参加派对的人数 $n$，朋友关系的条数 $p$ 和敌人关系的条数 $q$。
接下来 $p$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 是朋友关系。
接下来 $q$ 行，每行两个整数 $u, v$，表示 $u$ 和 $v$ 是敌人关系。

输出格式

输出一行一个整数，表示本次派对的握手次数。

样例 #1

样例输入 #1

4 2 2
1 2
2 3
1 4
1 3

样例输出 #1

3

提示

样例 1 解释

共有 $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ $6$ 对人。

• $(1,2)$ 是朋友，握手。
• $(1,3)$ 是敌人，不握手。
• $(1,4)$ 是敌人，不握手。
• $(2,3)$ 是朋友，握手。
• $(2,4)$ 是陌生人，但是 $1$ 是 $2$ 的朋友，也是 $4$ 的敌人，所以不握手。
• $(3,4)$ 是陌生人，但是不存在任何一个人既是 $3$ 和 $4$ 之一的敌人也是另一个人的朋友，故握手。

综上，一共握手 $3$ 次。

数据规模与约定

以下设 $m = p + q$，即 $m$ 是朋友和敌人关系条数之和。

• 对 $20%$ 的数据，保证 $m = 0$。
• 对 $50%$ 的数据，保证 $n, m \leq 100$。
• 对 $70%$ 的数据，保证 $n, m \leq 10^3$。
• 对 $100%$ 的数据，保证 $2 \leq n \leq 3 \times 10^4$，$1 \leq u, v \leq n$，$0 \leq p,q \leq m \leq 10^3$，$u \neq v$。同一对敌人或朋友关系不会出现两次，不会有一对人同时是敌人或朋友关系。

提示

• 本题的空间限制为 $2 \mathrm{GiB}$。这一空间限制意味着你可以在程序中开出不超过 $2147483648(>2 \times 10^9)$ 个 bool 或 char 的数组。注意，开不下同样大小的 int 数组。
• 请注意空间限制是你程序运行时所使用的空间峰值，其中还包括了函数压栈、其他变量等空间占用。所以请不要卡着上限开数组。
• 如果你开出了过大的数组，可能会导致编译错误。此时请酌情减小你的数组大小。
• 对于某些 32 位系统，或可用内存过少的系统，直接开出大小约为 2GB 的数组可能无法编译或无法运行。可以先把数组开小来测试样例，提交时再改回符合数据范围的数组，也可以使用洛谷在线 IDE 来测试样例。洛谷评测机保证可以正常评测。