luogu#P9008. [入门赛 #9] 大碗宽面 (Hard Version)
[入门赛 #9] 大碗宽面 (Hard Version)
题目背景
本题与 Easy Version 题意完全相同,仅有 的数据范围和空间限制不同。
扶苏和她的朋友们在 Impart 酒店开派对。
题目描述
算上扶苏,本次派对共有 个人。但是,并不是任何两个人都互相认识,并且互相认识的人关系也未必好。
具体而言,任意两个人可能是如下三种关系之一:
- 敌人
- 朋友
- 陌生人
派对的一大重要活动是相互握手。对任意两个人 ,他们之间的握手情况遵循下面的规则:
- 如果 和 是朋友关系,那么他们一定握手一次。
- 如果 和 是敌人关系,那么他们一定不握手。
- 如果 和 是陌生人关系,且存在一个人 ,使得 是 和 之一的朋友,同时是 中另一人的敌人,则 和 不会握手,否则 和 一定握手一次。
对第三条规则,简单的说法是:一对陌生人之间,如果某一方的朋友是另一方的敌人,则不握手,否则握手。
已知共有 对人是朋友关系, 对人是敌人关系。除了这 对人,其他每对人均为陌生人关系。
请你求出本次派对一共握手了多少次。
输入格式
第一行是三个整数,依次表示参加派对的人数 ,朋友关系的条数 和敌人关系的条数 。
接下来 行,每行两个整数 ,表示 和 是朋友关系。
接下来 行,每行两个整数 ,表示 和 是敌人关系。
输出格式
输出一行一个整数,表示本次派对的握手次数。
4 2 2
1 2
2 3
1 4
1 3
3
提示
样例 1 解释
共有 对人。
- 是朋友,握手。
- 是敌人,不握手。
- 是敌人,不握手。
- 是朋友,握手。
- 是陌生人,但是 是 的朋友,也是 的敌人,所以不握手。
- 是陌生人,但是不存在任何一个人既是 和 之一的敌人也是另一个人的朋友,故握手。
综上,一共握手 次。
数据规模与约定
以下设 ,即 是朋友和敌人关系条数之和。
- 对 的数据,保证 ,,,。同一对敌人或朋友关系不会出现两次,不会有一对人同时是敌人或朋友关系。
By 一扶苏一