Background

This problem has exactly the same statement as the Easy Version; only the constraints on $n$ and the memory limit are different.

Fusu and her friends are holding a party at the Impart Hotel.

Problem Description

Including Fusu, there are $n$ people at this party. However, not every pair of people know each other, and even if two people know each other, their relationship may not be good.

Specifically, any two people may have one of the following three relationships:

1. Enemies.
2. Friends.
3. Strangers.

One important activity at the party is shaking hands. For any two people $u, v$, whether they shake hands follows these rules:

1. If $u$ and $v$ are friends, then they must shake hands exactly once.
2. If $u$ and $v$ are enemies, then they must not shake hands.
3. If $u$ and $v$ are strangers, and there exists a person $w$ such that $w$ is a friend of one of $u$ and $v$ and also an enemy of the other one, then $u$ and $v$ will not shake hands; otherwise, $u$ and $v$ must shake hands exactly once.

For the third rule, a simpler wording is: for a pair of strangers, if one person’s friend is the other person’s enemy, then they do not shake hands; otherwise they shake hands.

It is known that there are $p$ pairs of friends and $q$ pairs of enemies. Apart from these $p + q$ pairs, every other pair of people are strangers.

Please compute how many handshakes happen in total at this party.

Input Format

The first line contains three integers, representing the number of people $n$, the number of friend relationships $p$, and the number of enemy relationships $q$, respectively.
The next $p$ lines each contain two integers $u, v$, indicating that $u$ and $v$ are friends.
The next $q$ lines each contain two integers $u, v$, indicating that $u$ and $v$ are enemies.

Output Format

Output one line with one integer, representing the total number of handshakes at this party.

4 2 2
1 2
2 3
1 4
1 3

3

Hint

Explanation for Sample 1

There are $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$, i.e. $6$ pairs of people in total.

• $(1,2)$ are friends, so they shake hands.
• $(1,3)$ are enemies, so they do not shake hands.
• $(1,4)$ are enemies, so they do not shake hands.
• $(2,3)$ are friends, so they shake hands.
• $(2,4)$ are strangers, but $1$ is a friend of $2$ and also an enemy of $4$, so they do not shake hands.
• $(3,4)$ are strangers, and there does not exist anyone who is an enemy of one of $3$ and $4$ and also a friend of the other, so they shake hands.

Therefore, there are $3$ handshakes in total.

Constraints

Let $m = p + q$, i.e. $m$ is the total number of friend and enemy relationships.

• For $100\%$ of the testdata, it is guaranteed that $2 \leq n \leq 10^6$, $1 \leq u, v \leq n$, $0 \leq p, q \leq m \leq 10^3$, $u \neq v$. No pair of enemies or friends will appear twice, and no pair of people will be both enemies and friends at the same time.

By Yifusu Yi

Translated by ChatGPT 5