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

Friends And Foes

Disjoint Set, Easy-Medium


Monk will be organizing a party as he recently got a promotion. He wants to invite his childhood classmates. Monk had a total of N classmates and a lot of them were friends with each other. There used to be \(M1\) friendship relations. However, time took its toll and some of them became enemies. A total of \(M2\) enemy relations are formed.

To avoid any nuisance in his party, Monk wants to invite only Special group of classmates in his party. Special group is the one where each person in the group is a friend of another and there should not be any two persons in that group who are enemies of each other. Now given the relationships among some of them, your task is to find the maximum number of classmates Monk can invite to his party.


1) Group of friends will be formed only by the given inputs. If given, A is a friend of B, B is a friend of C, then \(A,B,C\) forms a friendship group, and you cannot pick a subgroup from it.

2) Two people are said to be friends of each other if their friend relation is given or they are connected through a chain of mutual friends. For example, if given A is a friend of B, and B is a friend of C then A and C are friends.

3) Two people are said to be enemies of each other, only and only if their enemy relation is given. For example, if given A is a enemy of B, and B is a enemy of C, then A and C are not enemies of each other, unless it is given in the input.

4) There won't be any case, where both friend and enemy relation is given for two people.

The first line consists of integer N, denoting the number of Monk's classmates.
The second line consists of integer \(M1\) denoting the number of pair of friends.
The next \(M1\) lines consists of two integers of the form A and B who are friends with each other.
The next line consists of integer \(M2\) denoting the number of pair of enemies. The next \(M2\) lines consists of two integers of the form A and B who are enemies.

Print in a single line, the maximum number of friends Monk can invite to his party provided they should form a Special group.

\(1 \leq N \leq 10^5\)
\(1 \leq M1 + M2 \leq min ( 2\times10^5 , N\times (N-1)/2 ) \)
\(1 \leq A, B \leq N\)

1 2
1 3
4 5
2 3
2 4

According to the sample test case, there are 2 groups of friends.
\(Group 1\) consists of friend number 1, 2 and 3.
\(Group 2\) consists of friend number 4 and 5.
But since friend number 2 and 3 are enemies, Monk can not invite the first group to his party. Since, there are no enemy relations in the second group it is a Special group, therefore Monk will invite only the second group to his party which has 2 members.

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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

Code Monk (Disjoint Set Union (Union Find))

View All Notifications