#1775. [语言月赛202302] 大碗宽面

[语言月赛202302] 大碗宽面

题目描述

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

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

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

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

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

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

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

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

输入格式

第一行是三个整数,依次表示参加派对的人数 nn,朋友关系的条数 pp 和敌人关系的条数 qq。
接下来 pp 行,每行两个整数 u,vu,v,表示 uu 和 vv 是朋友关系。
接下来 qq 行,每行两个整数 u,vu, v,表示 uu 和 vv 是敌人关系。

输出格式

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

样例

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

题目来源:洛谷 B3712