from collections import defaultdict


class UnionFind:
    """
    Detailed info on union find data structure can be found at:
        http://a...content-available-to-author-only...n.edu/15uf/
    Complexity of merge is O(log*n), not O(logn). Detailed info can be found at:
        https://e...content-available-to-author-only...a.org/wiki/Iterated_logarithm
    """
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1] * size
        
    def _root(self, a):
        while self.parent[a] != a:
            self.parent[a] = self.parent[self.parent[a]]
            a = self.parent[a]
        return a
    
    def merge(self, a, b):
        a, b = self._root(a), self._root(b)
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]

    def __repr__(self):
        ret = defaultdict(list)
        for i in range(len(self.parent)):
            ret[self._root(i)].append(i)
        return "\n".join(str(v) for k, v in ret.items())


def find_same_contacts(contacts):
    """
    For each contact in contacts
        For each element in contact
            If element exists at seen_keys, merge contacts
            Otherwise add element to seen_keys with contact id as value
    Complexity is O(nlog*n)
    """
    union_find = UnionFind(len(contacts))
    seen_keys = {}
    for i, contact in enumerate(contacts):
        for elem in contact:
            if elem in seen_keys:
                union_find.merge(seen_keys[elem], i)
            else:
                seen_keys[elem] = i
    print(union_find)


the_contacts = [["Gaurav", "gaurav@gmail.com", "gaurav@gfgQA.com"],
                     ["Lucky", "lucky@gmail.com", "+1234567"],
                     ["gaurav123", "+5412312", "gaurav123@skype.com"],
                     ["gaurav1993", "+5412312", "gaurav@gfgQA.com"],
                     ["raja", "+2231210", "raja@gfg.com"],
                     ["bahubali", "+878312", "raja"]]

find_same_contacts(the_contacts)

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKCgpjbGFzcyBVbmlvbkZpbmQ6CiAgICAiIiIKICAgIERldGFpbGVkIGluZm8gb24gdW5pb24gZmluZCBkYXRhIHN0cnVjdHVyZSBjYW4gYmUgZm91bmQgYXQ6CiAgICAgICAgaHR0cDovL2EuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLm4uZWR1LzE1dWYvCiAgICBDb21wbGV4aXR5IG9mIG1lcmdlIGlzIE8obG9nKm4pLCBub3QgTyhsb2duKS4gRGV0YWlsZWQgaW5mbyBjYW4gYmUgZm91bmQgYXQ6CiAgICAgICAgaHR0cHM6Ly9lLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5hLm9yZy93aWtpL0l0ZXJhdGVkX2xvZ2FyaXRobQogICAgIiIiCiAgICBkZWYgX19pbml0X18oc2VsZiwgc2l6ZSk6CiAgICAgICAgc2VsZi5wYXJlbnQgPSBbaSBmb3IgaSBpbiByYW5nZShzaXplKV0KICAgICAgICBzZWxmLnNpemUgPSBbMV0gKiBzaXplCiAgICAgICAgCiAgICBkZWYgX3Jvb3Qoc2VsZiwgYSk6CiAgICAgICAgd2hpbGUgc2VsZi5wYXJlbnRbYV0gIT0gYToKICAgICAgICAgICAgc2VsZi5wYXJlbnRbYV0gPSBzZWxmLnBhcmVudFtzZWxmLnBhcmVudFthXV0KICAgICAgICAgICAgYSA9IHNlbGYucGFyZW50W2FdCiAgICAgICAgcmV0dXJuIGEKICAgIAogICAgZGVmIG1lcmdlKHNlbGYsIGEsIGIpOgogICAgICAgIGEsIGIgPSBzZWxmLl9yb290KGEpLCBzZWxmLl9yb290KGIpCiAgICAgICAgaWYgc2VsZi5zaXplW2FdIDwgc2VsZi5zaXplW2JdOgogICAgICAgICAgICBhLCBiID0gYiwgYQogICAgICAgIHNlbGYucGFyZW50W2JdID0gYQogICAgICAgIHNlbGYuc2l6ZVthXSArPSBzZWxmLnNpemVbYl0KCiAgICBkZWYgX19yZXByX18oc2VsZik6CiAgICAgICAgcmV0ID0gZGVmYXVsdGRpY3QobGlzdCkKICAgICAgICBmb3IgaSBpbiByYW5nZShsZW4oc2VsZi5wYXJlbnQpKToKICAgICAgICAgICAgcmV0W3NlbGYuX3Jvb3QoaSldLmFwcGVuZChpKQogICAgICAgIHJldHVybiAiXG4iLmpvaW4oc3RyKHYpIGZvciBrLCB2IGluIHJldC5pdGVtcygpKQoKCmRlZiBmaW5kX3NhbWVfY29udGFjdHMoY29udGFjdHMpOgogICAgIiIiCiAgICBGb3IgZWFjaCBjb250YWN0IGluIGNvbnRhY3RzCiAgICAgICAgRm9yIGVhY2ggZWxlbWVudCBpbiBjb250YWN0CiAgICAgICAgICAgIElmIGVsZW1lbnQgZXhpc3RzIGF0IHNlZW5fa2V5cywgbWVyZ2UgY29udGFjdHMKICAgICAgICAgICAgT3RoZXJ3aXNlIGFkZCBlbGVtZW50IHRvIHNlZW5fa2V5cyB3aXRoIGNvbnRhY3QgaWQgYXMgdmFsdWUKICAgIENvbXBsZXhpdHkgaXMgTyhubG9nKm4pCiAgICAiIiIKICAgIHVuaW9uX2ZpbmQgPSBVbmlvbkZpbmQobGVuKGNvbnRhY3RzKSkKICAgIHNlZW5fa2V5cyA9IHt9CiAgICBmb3IgaSwgY29udGFjdCBpbiBlbnVtZXJhdGUoY29udGFjdHMpOgogICAgICAgIGZvciBlbGVtIGluIGNvbnRhY3Q6CiAgICAgICAgICAgIGlmIGVsZW0gaW4gc2Vlbl9rZXlzOgogICAgICAgICAgICAgICAgdW5pb25fZmluZC5tZXJnZShzZWVuX2tleXNbZWxlbV0sIGkpCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBzZWVuX2tleXNbZWxlbV0gPSBpCiAgICBwcmludCh1bmlvbl9maW5kKQoKCnRoZV9jb250YWN0cyA9IFtbIkdhdXJhdiIsICJnYXVyYXZAZ21haWwuY29tIiwgImdhdXJhdkBnZmdRQS5jb20iXSwKICAgICAgICAgICAgICAgICAgICAgWyJMdWNreSIsICJsdWNreUBnbWFpbC5jb20iLCAiKzEyMzQ1NjciXSwKICAgICAgICAgICAgICAgICAgICAgWyJnYXVyYXYxMjMiLCAiKzU0MTIzMTIiLCAiZ2F1cmF2MTIzQHNreXBlLmNvbSJdLAogICAgICAgICAgICAgICAgICAgICBbImdhdXJhdjE5OTMiLCAiKzU0MTIzMTIiLCAiZ2F1cmF2QGdmZ1FBLmNvbSJdLAogICAgICAgICAgICAgICAgICAgICBbInJhamEiLCAiKzIyMzEyMTAiLCAicmFqYUBnZmcuY29tIl0sCiAgICAgICAgICAgICAgICAgICAgIFsiYmFodWJhbGkiLCAiKzg3ODMxMiIsICJyYWphIl1dCgpmaW5kX3NhbWVfY29udGFjdHModGhlX2NvbnRhY3RzKQ==