Unique People in Contact List

You are given a two-dimensional list of strings contacts. Each element contacts[i] represents the list of emails for contact i. Contact i is considered a duplicate if there’s a j < i such that contact j shares a common email with i. Return the number of unique people in contacts.

Constraints

• 0 ≤ n ≤ 100,000 where n is the total number of strings in contacts

https://binarysearch.com/problems/Unique-People-in-Contact-List

Examples

Example 1

Input

• contacts = [['[email protected]', '[email protected]'], ['[email protected]', '[email protected]'], ['[email protected]']]

Output

• answer = 2

Explanation

Contact 0 and 1 are the same person since they share a common email "[email protected]". Then, contact 2 is another person.

Example 2

Input

• contacts = [['[email protected]'], ['[email protected]'], ['[email protected]']]

Output

• answer = 3

Explanation

All 3 contacts represent 3 unique people.

Example 3

Input

• contacts = [['[email protected]'], ['[email protected]', '[email protected]'], ['[email protected]']]

Output

• answer = 1

Explanation

Only contact i = 0 is considered unique. The other two contacts are duplicates.

Solution