All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Marriage Problem
Tag(s):

Disjoint Set, Easy-Medium

Problem
Editorial
Analytics

Monk has recently created a matrimonial site. $$X$$ men and $$Y$$ women registered there. As Monk has access to everyone's Facebook profile, he can see whether a person is a friend of another person or not. He doesn't want any two people who are in a single group to get married together. So, first we have $$q_1$$ relationships among men. Then, we have $$q_2$$ relationships among women. Finally we have $$q_3$$ relationships among men and women. Read the input format for more clarity. Now, Monk wants to calculate the total number of unique marriages he can set between men and women provided the conditions are followed.
Note - Two person are said to be in a group if they are friends directly or connected through a chain of mutual friends.

Input:
The first line consists of $$X$$ and $$Y$$.
Next line consists of variable $$q_1$$.
The next $$q_1$$ lines will have two integers of the form $$A$$ $$B$$ where $$A$$ and $$B$$ are both men and are friends on facebook and $$A \neq B$$.
Next line consists of variable $$q_2$$.
The next $$q_2$$ lines will have two integers of the form $$A$$ $$B$$ where $$A$$ and $$B$$ are both women and are friends on facebook and $$A \neq B$$.
Next line consists of variable $$q_3$$.
The next $$q_3$$ lines will have two integers of the form $$A$$ $$B$$ where $$A$$ is a man and $$B$$ is a woman and they both are friends on facebook.

Output:
Print in a single line the answer.

Constraints:
$$1 \leq X, Y \leq 10^6$$
$$1 \leq q_1, q_2, q_3 \leq 10^6$$
If $$A$$ is a man, then $$1 \leq A \leq X$$
If $$A$$ is a woman, then $$1 \leq A \leq Y$$
If $$B$$ is a man, then $$1 \leq B \leq X$$
If $$B$$ is a woman, then $$1 \leq B \leq Y$$

SAMPLE INPUT
4 5
1
1 3
2
1 4
1 5
2
1 2
4 1
SAMPLE OUTPUT
15
Explanation

In the sample test case, there are $$4$$ groups.
$$Group1 - Man1, Man3, Woman2$$
$$Group2 - Man4, Woman1, Woman4, Woman5$$
$$Group3 - Man2$$
$$Group4 - Woman3$$
The men in $$Group1$$ can marry $$4$$ women = $$8$$ possibilities
The single man in $$Group2$$ can marry $$2$$ women = $$2$$ possibilities
The single man in $$Group3$$ can marry $$5$$ women = $$5$$ possibilities

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Disjoint Set Union (Union Find))

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications