SOLVE
LATER
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\)
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
Challenge Name
Code Monk (Disjoint Set Union (Union Find))
Code Monk (Disjoint Set Union (Union Find))