{"problem":{"name":"[入门赛 #9] 大碗宽面 (Hard Version)","description":{"content":"算上扶苏，本次派对共有 $n$ 个人。但是，并不是任何两个人都互相认识，并且互相认识的人关系也未必好。 具体而言，任意两个人可能是如下三种关系之一： 1. 敌人 2. 朋友 3. 陌生人 派对的一大重要活动是相互握手。对任意两个人 $u,v$，他们之间的握手情况遵循下面的规则： 1. 如果 $u$ 和 $v$ 是朋友关系，那么他们一定握手一次。 2. 如果 $u$ 和 $v$ 是敌人关系，那么","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9008"},"statements":[{"statement_type":"Markdown","content":"算上扶苏，本次派对共有 $n$ 个人。但是，并不是任何两个人都互相认识，并且互相认识的人关系也未必好。\n\n具体而言，任意两个人可能是如下三种关系之一：\n1. 敌人\n2. 朋友\n3. 陌生人\n\n派对的一大重要活动是相互握手。对任意两个人 $u,v$，他们之间的握手情况遵循下面的规则：\n1. 如果 $u$ 和 $v$ 是朋友关系，那么他们一定握手一次。\n2. 如果 $u$ 和 $v$ 是敌人关系，那么他们一定**不**握手。\n3. 如果 $u$ 和 $v$ 是陌生人关系，且存在一个人 $w$，使得 $w$ 是 $u$ 和 $v$ 之一的朋友，同时是 $u,v$ 中另一人的敌人，则 $u$ 和 $v$ **不会**握手，否则 $u$ 和 $v$ 一定握手一次。\n\n对第三条规则，简单的说法是：一对陌生人之间，如果某一方的朋友是另一方的敌人，则不握手，否则握手。\n\n已知共有 $p$ 对人是朋友关系，$q$ 对人是敌人关系。除了这 $p + q$ 对人，其他每对人均为陌生人关系。\n\n请你求出本次派对一共握手了多少次。\n\n## Input\n\n第一行是三个整数，依次表示参加派对的人数 $n$，朋友关系的条数 $p$ 和敌人关系的条数 $q$。  \n接下来 $p$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 是朋友关系。  \n接下来 $q$ 行，每行两个整数 $u, v$，表示 $u$ 和 $v$ 是敌人关系。\n\n## Output\n\n输出一行一个整数，表示本次派对的握手次数。\n\n[samples]\n\n## Background\n\n**本题与 Easy Version 题意完全相同，仅有 $n$ 的数据范围和空间限制不同**。\n\n扶苏和她的朋友们在 Impart 酒店开派对。\n\n## Note\n\n### 样例 1 解释\n\n共有 $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ $6$ 对人。\n- $(1,2)$ 是朋友，握手。\n- $(1,3)$ 是敌人，不握手。\n- $(1,4)$ 是敌人，不握手。\n- $(2,3)$ 是朋友，握手。\n- $(2,4)$ 是陌生人，但是 $1$ 是 $2$ 的朋友，也是 $4$ 的敌人，所以不握手。\n- $(3,4)$ 是陌生人，但是不存在任何一个人既是 $3$ 和 $4$ 之一的敌人也是另一个人的朋友，故握手。\n\n综上，一共握手 $3$ 次。\n\n### 数据规模与约定\n\n以下设 $m = p + q$，即 $m$ 是朋友和敌人关系条数之和。\n\n- 对 $100\\%$ 的数据，保证 $2 \\leq n \\leq 10^6$，$1 \\leq u, v \\leq n$，$0 \\leq p,q \\leq m \\leq 10^3$，$u \\neq v$。同一对敌人或朋友关系不会出现两次，不会有一对人同时是敌人或朋友关系。\n\nBy 一扶苏一","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9008","tags":["2023","O2优化","语言月赛"],"sample_group":[["4 2 2\n1 2\n2 3\n1 4\n1 3","3"]],"created_at":"2026-03-03 11:09:25"}}