luogu#P9008. [入门赛 #9] 大碗宽面 (Hard Version)

[入门赛 #9] 大碗宽面 (Hard Version)

题目背景

本题与 Easy Version 题意完全相同,仅有 nn 的数据范围和空间限制不同

扶苏和她的朋友们在 Impart 酒店开派对。

题目描述

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

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

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

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

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

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

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

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

输入格式

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

输出格式

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

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

提示

样例 1 解释

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

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

综上,一共握手 33 次。

数据规模与约定

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

  • 100%100\% 的数据,保证 2n1062 \leq n \leq 10^61u,vn1 \leq u, v \leq n0p,qm1030 \leq p,q \leq m \leq 10^3uvu \neq v。同一对敌人或朋友关系不会出现两次,不会有一对人同时是敌人或朋友关系。

By 一扶苏一